🟩 [백준] [Python] [구현] 10815번_숫자 카드

문제

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

10815번: 숫자 카드

풀이

# 백준 10815번 문제 - 숫자 카드
import sys
input = sys.stdin.readline
n = int(input())
arr = set(map(int,input().split()))
m = int(input())
m_arr= list(map(int,input().split()))

for i in range(m):
    if m_arr[i] in arr : 
        print(1,end=' ')
    else : print(0,end=' ')

처음에 문제를 보고 매우 쉬운 문제라고 생각했다. 그런데 입력값이 매우 크기 때문에 시간복잡도를 생각해야 했다.

리스트 탐색의 시간 복잡도는 O(n)이지만 Set을 사용하면 O(1) 이므로 Set 자료형을 사용하여 해결하면 시간초과가 뜨지 않는다.

또한 이분탐색으로도 문제를 해결 할 수 있다. 

# 이분탐색
import sys

n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().split()))

card.sort()

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


for i in range(m):
    if binary_search(card, check[i], 0, n - 1) is not None:
        print(1, end=' ')
    else:
        print(0, end=' ')