[백준 10815번] 숫자 카드 (파이썬)

문제

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

답

시행착오

import sys
input = sys.stdin.readline

N = int(input())
Card_list = list(map(int, input().split()))
M = int(input())
Num_list = list(map(int, input().split()))

Ans = []
for i in Num_list:
  if i in Card_list:
    Ans.append(1)
  else:
    Ans.append(0)
print(*Ans)

 

Num_list를 list로 했더니 시간초과가 되었다.

set으로 바꾸니까 통과했다.

 

<if i in Card_list>를 했을 때,

list는 순서대로 검색해서 O(n)이고

set은 해쉬테이블로 구현되서 O(1)이다.

답

import sys
input = sys.stdin.readline

N = int(input())
Card_list = set(map(int, input().split()))
M = int(input())
Num_list = list(map(int, input().split()))

Ans = []
for i in Num_list:
  if i in Card_list:
    Ans.append(1)
  else:
    Ans.append(0)
print(*Ans)