[BOJ / Python] 10815 숫자 카드

문제

백준 10815 숫자 카드

코드

1. 부족한 코드 -- 시간 초과

import sys

n = int(sys.stdin.readline())
my_cards = sorted(list(map(int, sys.stdin.readline().split())))
m = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))

result = []
for x in cards:
    if x in my_cards:
        result.append(1)
    else:
        result.append(0)

print(*result)

코드 설명
PyCharm에서 돌려보면 결괏값을 잘 출력하는 코드이긴 하다.
하지만 내가 가진 카드와 검사해야할 카드가 많아질수록 결과를 내는데 걸리는 시간이 기하급수적으로 길어진다.
그래서 백준에 해당 코드를 제출했을 땐 시간초과가 나왔다.

2-1. 더 나은 코드: 딕셔너리 자료형 사용하기

import sys

n = int(sys.stdin.readline())
my_cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))

result = []
check = {}
for i in range(len(my_cards)):
    check[my_cards[i]] = 7

for i in range(m):
    if cards[i] in check:
        result.append(1)
    else:
        result.append(0)

print(*result)

코드 설명
이 풀이의 핵심은 그 값이 있냐 없냐를 빠르게 확인할 수 있는 방법으로 딕셔너리 자료형을 사용했다는 것이다.
우선 내가 가진 카드들을 모두 딕셔너리에 넣는다. 이때 각각의 카드에 대응시킨 value 값은 무엇이든 상관없다. (나는 임의로 7을 넣었다.) 그리고 검사해야할 카드들에 대하여 그 카드에 적힌 숫자가 딕셔너리에 있는지 없는지 검사하면 된다.

2-2. 더 나은 코드: 이진 탐색 사용하기

n = int(sys.stdin.readline())
my_cards = sorted(list(map(int, sys.stdin.readline().split())))
m = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))

for x in cards:
    low, high = 0, n-1
    exist = False
    while low <= high:
        mid = (low + high) // 2
        if my_cards[mid] > x:
            high = mid - 1
        elif my_cards[mid] < x:
            low = mid + 1
        else:
            exist = True
            break
    print(1 if exist else 0, end=" ")

또 다른 풀이가 없을까 찾아보다가 이진 탐색을 이용한 풀이도 가능함을 알게 되었다.
우선 이진 탐색을 사용하려면 자료가 정렬되어있어야 한다. 따라서 내가 가진 카드들 my_cards를 정렬시킨다.
다음 이진 탐색 알고리즘을 사용하여 코드를 작성하면 된다.