6. Check If N and Its Double Exist

문제

배열 속 한 요소가 다른 요소의 두 배인 경우가 존재하는지 찾기.

(배열 속에 n, m이 존재하는지 찾기. m = n * 2)

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

 

내가 해결한 방식(c++)

한 요소마다 전체 배열을 한 번씩 검색 => time complexity O(n²)으로 느림

0이 두 번 들어가는 경우 true가 아닌 false 반환 => 잘못된 결과

bool checkIfExist(int* arr, int arrSize){
    for (int i = 0; i < arrSize; i++){
        for (int j = 0; j < arrSize; j++){
            // arr[j]에 2를 곱하면 arr[i]가 되는지 확인
            if (arr[j] != 0 && arr[j] == (arr[i] * 2)){
                return true;
            // arr[j]가 짝수라면, 2로 나누었을 때 arr[i]가 되는지 확인
            } else if (arr[j] != 0 && arr[j] % 2 == 0 && arr[j] == (arr[i] / 2)){
                return true;
            } 
        }
    }
    return false;
}

 

다른 해결 방식(python)

검색 속도가 빠른 set 사용. 

arr를 iterate하며

현재 요소 * 2나 현재요소 / 2가 set에 있는지 확인 -> 있으면 true 반환.

없으면 -> 현재 요소를 set에 추가.

def checkIfExist(self, arr: List[int]) -> bool:
    ref = set()

    for num in arr:
        if num * 2 in ref or num / 2 in ref:
            return True
        ref.add(num)

    return False