백준 10815 - 숫자 카드

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

10815번: 숫자 카드

import sys

input = sys.stdin.readline

n = int(input())
set_a = set(map(int, input().split()))
m = int(input())
list_a = list(map(int, input().split()))
ans = []
for num in list_a:
    if num in set_a:
        ans.append(1)
    else:
        ans.append(0)

print(*ans)

비교해야 할 리스트의 길이가 최대 500000이기 때문에, 탐색에 O(n)이 걸리는 리스트로는 두 리스트를 모두 순차적으로 탐색하려면 500000의 제곱에 달하는 시간이 소요된다. 따라서 해당 방법은 시간초과에 걸릴 가능성이 높다.

 

그러므로, 탐색에 O(1)이 걸리는 해시테이블 계열의 자료구조를 쓰는 것이 좋다. 그래서 처음 입력받는 배열을 set 형태로 생성해서 값을 저장한다.

 

이후 두 번째 배열은 리스트로 받고, 해당 값이 set에 있는지만 체크해서 있으면 1, 없으면 0을 배열에 담은 뒤 배열의 값을 출력한다.