백준 1920번 수 찾기 파이썬 python

선행 지식

1. List 와 Set에서의 in 연사자 성능 차이

list 자료형에서는 in 연산자의 시간 복잡도는 O(n)이다. ==> 앞에서 부터 차례로 하나하나 비교해 나간다.

set 자료형에서는 in 연산자의 시간 복잡도는 O(1)이다. ==> 어떤 숫자를 찾던 같은 시간이 걸린다.

ex) list(range(1,1000000))와 set(range(1,1000000))

(1번 상황) 숫자 1을 찾아라

 1 in 리스트

>>> 0초에 가까운 시간

1 in set

>>> 0.5초 (예시)

(2번 상황)

100000 in 리스트

>>> 100초

100000 in set 

>>>0.5초

 

정리

List 자료형은 선형적으로 시간이 늘어나고, Set 자료형은 일정하다.

결론

많은 양의 데이터에서의  in을 사용할 때는 set 자료형을 사용하자.

2. Generator(제네레이터) - 몰라도 풀기 가능

 

 

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

1920번: 수 찾기

문제 요약

M개의 숫자들이 N개의 숫자들에 포함 여부를 차례로 출력해라.

>>>N개의 숫자들의 순서는 상관없고, 포함 여부만 확인(M은 순서 상관 있음)

 

문제 해결

n=int(input())
s=set(map(int,input().split())) #핵심! 많은 양의 데이터에서 in연산자를 사용해야하기 때문
m=int(input())
def g(l): 
    for i in l:
        yield i 
x=g(list(map(int,input().split())))
for i in x:
    print(1 if i in s else 0)

결과

Generator를 사용하여 큰 데이터를 전부 메모리에 할당하지 않고 그때 그때 호출하여 사용할 수 있게 함으로서

메모리의 절약과 시간 절약이 되지 않았나 싶다.

 

 

제네레이터 미사용, 리스트로 해결

n=int(input())
s=set(map(int,input().split()))
m=int(input())
x=list(map(int,input().split()))
for i in x:
    print(1 if i in s else 0)

결과

150MB사용하여 문제 해결을 했으나, 128MB제한으로 실패로 봐도 무방하지 않을까싶다.