백준 1920: 수 찾기

✔ 풀이를 위한 아이디어

• 이분탐색 (Binary Search) 의 활용 (복습)
  
  

✔ 코드

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A = sorted(A)
M = int(sys.stdin.readline())
Q = list(map(int, sys.stdin.readline().split()))

start = 0
end = N - 1
for i in range(M):
    while True:
        mid = (start + end) // 2
        if start > end:
            print("0")
            break
        elif Q[i] < A[mid]:
            end = mid - 1
        elif Q[i] > A[mid]:
            start = mid + 1
        elif Q[i] == A[mid]:
            print("1")
            break

    start = 0
    end = N - 1

• 리스트 A를 sorted 함수를 활용해 정렬한 뒤, Q에 있는 요소들을 하나씩 이분탐색 해나가면 풀리는 간단한 문제이다.
• 정렬 알고리즘 대신 sorted 함수를 사용하고, 1씩 증가시키며 탐색하는 것보다 이분탐색 하는 것이 훨씬 시간복잡도를 감소시킨다는 사실을 이전의 문제풀이를 통해 깨달았기 때문에 시행착오 없이 성공할 수 있었다.

✔ 관련 개념

• 이분탐색 알고리즘: https://satisfactoryplace.tistory.com/39

오늘 정말 피곤한 하루였는데, 그래도 1일 1백준을 실천했다!