[백준 1920] 수 찾기

www.acmicpc.net/problem/1920

1920번: 수 찾기

---

접근

처음에는 단순하게 리스트에 N개의 수를 넣고 또 다른 리스트에 M개의 수를 넣어 for문으로 탐색하면서 in연산을 사용하였다. 하지만 리스트를 탐색하는 것은 O(N)의 시간복잡도가 발생하여 시간초과가 발생하였다.

 

이를 set이나 dict 자료형을 사용하면 O(1)의 시간복잡도를 갖기 때문에 효율적이라는 것을 알게되었다. 

 

구현

N개의 수를 set 자료형으로 입력받으며 numbers에 있는 M개의 수를 in으로 비교한다.

이때 O(1)의 시간복잡도가 발생하여 리스트로 탐색하는 것보다 효율적이다.

import sys
input = sys.stdin.readline

N = int(input())
numbers_set = set(map(int, input().split()))

M = int(input())
numbers = list(map(int, input().split()))

for i in range(M):
    if numbers[i] in numbers_set:
        print(1)
    else:
        print(0)