[🥈4 / 백준 10815 / 파이썬] 숫자 카드

 

10815번: 숫자 카드

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

예제 입력  5 6 3 2 10 -10 8 10 9 -5 2 3 4 5 -10

예제 출력  1 0 0 1 1 0 0 1

 

풀이

 

배열에 특정 원소가 있는지 검사하는 문제이다.

 

숫자 카드의 개수가 최대 50만 개로 상당히 많다.

List 형을 사용할 경우 List안의 특정 원소가 있는지 검사하기 위해

항목이 나올 때까지 모든 원소를 순회해야 한다.

즉, 탐색의 시간복잡도가 O(N)이기 때문에 O(N^2), 즉 500,000 x 500,000 이 되어버려서 시간초과가 뜬다.

 

따라서 다른 자료형을 사용해야 한다.

set, dict의 경우 순서와 인덱스 없이 구성되므로 모든 원소를 순회할 필요가 없다.

즉, 값이 있는 곳만 펼쳐보면 되기 때문에 시간복잡도가 O(1)에 해당한다.

 

set나 dict 중 원하는 것으로 자료를 구성하고 비교해주도록 하자.

 

import sys
input = sys.stdin.readline
r = []

# n과 m은 사용하지 않을 것이므로 굳이 변수로 저장할 필요가 없다.
int(input())
c = set(list(map(int,input().split())))
    
int(input())
for i in list(map(int,input().split())):
    if i in c:
        r.append(1)
    else:
        r.append(0)
print(*r)