10815 숫자 카드

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

내 풀이(맞음)

def binary_search(array, target, start, end):
    mid = (start + end) // 2
    if start > end:
        return None
    if target == array[mid]:
        return mid
    elif target < array[mid]:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)
        
n = int(input())
ary = list(map(int, input().split()))
ary.sort()
m = int(input())
lst = list(map(int, input().split()))
chk = [0] * m

for i in range(m):
    x = binary_search(ary, lst[i], 0, n-1)
    if x == None:
        continue
    else:
        chk[i] = 1

for i in chk:
    print(i, end = " ")

예전엔 못 푼 문제다 하지만 "이것이 취업을 위한 코딩테스트다" 책을 보고 공부를 하고 풀어보니까 바로 이진 탐색을 사용해야 겠다고 생각했다.

하지만 문제를 풀 때 정렬을 하지 않고서 풀어서 처음에 틀렸다. 이진 탐색은 꼭 정렬이 완료된 상태에서 사용해야 한다는 것을 다시 한번 기억해야겠다.