[백준 10815 실버5] 숫자 카드(이분 탐색/Python) 복습 -/3

1. 파이썬 dictionary 이용

import sys

N = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().split()))

_dict = {}  # 속도는 dictionary!
for i in range(len(cards)):
    _dict[cards[i]] = 0  # 아무 숫자로 mapping

for j in range(M):
    if checks[j] not in _dict:
        print(0, end=' ')
    else:
        print(1, end=' ')

2. sort 후 이분 탐색 이용

import sys

N = int(sys.stdin.readline())
cards = sorted(list(map(int, sys.stdin.readline().split())))
M = int(sys.stdin.readline())
checks = list(map(int, sys.stdin.readline().split()))

for check in checks:
    low, high = 0, N-1  # cards의 이진 탐색 index
    exist = False
    while low <= high:
        mid = (low + high) // 2
        if cards[mid] > check:  # 중간 값보다 작다면
            high = mid - 1  # 중간보다 왼쪽 한 칸 옆까지 탐색
        elif cards[mid] < check:  # 중간 값보다 크다면
            low = mid + 1  # 중간보다 오른쪽 한 칸 옆부터 탐색
        else:
            exist = True
            break
    print(1 if exist else 0, end=' ')

비교: 파이썬 dict 이용한 기법이 훨씬 빠르다.
그렇지만 이분 탐색 기법을 배워두는게 좋으니 복습이 필요함.
Sort 알고리즘의 시간복잡도는 o(nlogn) 이라고.
Sort 보다도 파이썬 dict를 쓰는게 훨씬 좋았다.

복습 횟수:
0차 공부 - 4.1 완
1차 복습
2차 복습
3차 복습