99클럽 TIL (240804)

[Middler] 숫자카드

걸린시간 : 30분

 

오늘의 회고

M개의 숫자에 대해 N개의 숫자 배열에 존재하는 지 확인하는 문제로 N과 M의 범위 1이상 500,000 이하이기 때문에 2중 포문으로 작성 시 O(N^2)은 시간 초과가 발생할 수 있다고 생각했다.

 

이진탐색은 O(logN)의 시간복잡도로 비교 대상이 N개 이기 때문에 O(NlogN) 복잡도가 걸릴 수 있다고 판단했다. 대략적으로 500,000 log500,000 = 약 10,000,000 으로 이진탐색을 활용해 해결할 수 있습니다.

 

문제 풀이

1. python

N = int(input())
arr1 = sorted(list(map(int, input().split())))
M = int(input())
arr2 = list(map(int, input().split()))

# 이진탐색 nlogn의 시간복잡도 

answer = [ 0 for _ in range(M) ]
for num, target in enumerate(arr2) :
    start = 0
    end = len(arr1) - 1
    
    while start <= end :
        mid = (start + end) // 2
        
        if target == arr1[mid] :
            answer[num] = 1
            break
        elif target <= arr1[mid] :
            end = mid - 1
        else :
            start = mid + 1
    
print(' '.join(map(str, answer)))

 

느낀 점

- 이진탐색은 틀을 외워두고 있자!