[백준] 숫자 카드

쏠로몬·2021년 12월 5일
0

접근 방법 : 이분탐색

처음에 봤을 때는 그냥 단순 비교하면 될 줄 알고 코드를 때려 박았더니 역시나 안됐다.

이분탐색으로 풀어야 시간 초과가 안남.

비교 전에 sort 해주는 것 잊지 않기.

import sys

N = int(sys.stdin.readline().strip())
card_list = list(map(int, sys.stdin.readline().strip().split()))
M = int(sys.stdin.readline().strip())
compare_list = list(map(int, sys.stdin.readline().strip().split()))

card_list.sort()

for i in range(M):
    low, high = 0, N - 1
    while low <= high:
        mid = (high + low) // 2
        if card_list[mid] == compare_list[i]:
            print(1, end=" ")
            break
        elif card_list[mid] < compare_list[i]:
            low = mid + 1
        else:
            high = mid - 1

        if low > high:
            print(0, end=" ")
            break
profile
이사가요~ 티스토리 블로그 입니다. https://help-solomon.tistory.com/

0개의 댓글