백준 (boj) 10815 파이썬 - 숫자 카드

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

10815번: 숫자 카드

 

시간초과를 유발하는 문제였다. 

이런 문제처럼 순서와 중복에 대한 특성을 사용하지 않을때는 list보다는 set을 사용하는게 좋다고 한다.

if num in arr : print(x)

예를들면 위 코드처럼, 어떤 집합에 포함되어 있는지 확인할때? 리스트는 인덱스 0부터 n까지 일일이 검사를 해야하므로 시간복잡도가 O(n) 이고, set은 O(1)이라고 한다.

이 문제에서도 list를 단지 set으로 바꾸었을 뿐인데 시간초과로부터 해방될수 있었다.

 

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=' ')