[백준 1920] 수 찾기 - 해시, 이분탐색, Counter, Set

코드1 - Counter

from collections import Counter

n = int(input())
arr1 = map(int, input().split())
arr1 = Counter(arr1)

m = int(input())
arr2 = map(int, input().split())

for num in arr2:
    if num in arr1:
        print('1')
    else:
        print('0')

 

 

첫 배열을 Counter 를 이용해 dict 자료구조로 바꾼 뒤, in으로 탐색한다. O(1) 이므로 통과

 

코드2 - set

n = int(input())
arr1 = map(int, input().split())
arr1 = set(arr1)

m = int(input())
arr2 = map(int, input().split())

for num in arr2:
    if num in arr1:
        print('1')
    else:
        print('0')

set 도 검색 시 O(1) 이기 때문에 value가 필요없는 dict 대신 사용가능

 

코드3 - 이분탐색

n = int(input())
arr1 = list(map(int, input().split()))
arr1.sort()
m = int(input())
arr2 = map(int, input().split())

for num in arr2:
    start = 0
    end = len(arr1) - 1
    flag = False
    while start <= end:
        mid = (start + end) // 2
        if arr1[mid] == num:
            flag = True
            break
        elif arr1[mid] > num:
            end = mid - 1
        elif arr1[mid] < num:
            start = mid + 1
    if flag:
        print('1')
    else:
        print('0')

arr2에 들어있는 수를 이분 탐색을 이용해 검색한다.

 

결과

위에서부터 코드3 (이분탐색), 코드2 (set), 코드1 (Counter) 인데 O(1) 과 O(log N) 차이가 난다.