[Baekjoon] 10815 숫자 카드 (실버 V) - Python

10815 숫자 카드 (실버 V) - Python

처음에는 단순히 2중 반복문을 이용하여 순차탐색을 진행하였다. 하지만 시간 복잡도가 O(n^2)으로 시간초과가 났다.

N = int(input())
cards = [int(x) for x in input().split()]
M = int(input())
find_card = [int(x) for x in input().split()]
exists = [0] * M

for i in range(0, M):
    for j in range(0, N):
        if find_card[i] == cards[j]:
            exists[i] = 1

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

 

다음 코드에서 반복문을 하나 줄여서 시간 복잡도를 낮췄지만 여전히 시간 초과가 났다.

N = int(input())
cards = [int(x) for x in input().split()]
M = int(input())
find_card = [int(x) for x in input().split()]
exists = [0] * M

for i in range(0, M):
    if find_card[i] in cards:
        exists[i] = 1

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

 

입력 받는 것도 sys 모듈을 이용하고 이진탐색을 함수로 구현하여 시간 복잡도를 O(log n)정도로 낮추었더니 문제가 해결되었다.

import sys

N = int(sys.stdin.readline())
cards = [int(x) for x in sys.stdin.readline().split()]
M = int(sys.stdin.readline())
find_card = [int(x) for x in sys.stdin.readline().split()]
cards.sort()

def binary_search(x):
    start = 0
    end = N - 1
    while start <= end:
        mid = (start + end) // 2
        if cards[mid] == x:
            return 1
        elif cards[mid] > x:
            end = mid - 1
        else:
            start = mid + 1

    return 0

for i in find_card:
    print(binary_search(i), end=" ")

 

시간 초과 문제가 난다면 이진탐색을 떠올리자.