[파이썬] 리스트, 딕셔너리 시간 복잡도 체감하기

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

1920번: 수 찾기

---

사실 list가 찾는데 시간이 오래걸린다고 듣긴 했어도 확 체감이 없었는데 이 문제 하나로 엄청나게 체감이 되서 블로그 글을 작성한다.

문제를 잘 살펴보자, 실버4 문제에 수찾기... 매우 간단해보인다.

근데.. 정답비율이 뭔가 이상한데? 29.997% 자그마치 30%가 안된다.

여기서 조건을 살펴보면 시간 제한 1초, 메모리 제한 128MB => 이러면 list나 queue에 너무 많은 데이터가 들어와도 안되고 입력 수에 따라 시간 초과가 날 수도 있다.

여기서 입력 개수를 살펴보면 N <= 100,000, M <= 100,000

그러면 아마 이중 for문이 나오면 무조건 실패 할 것이고, 아마 list만 사용하면 가능하지 않을까? 라고 문제를 접근해서 풀었더니,

정말 깔끔한 시간초과다..... 그래서 혹시 진짜 궁금해서 dictionary로 코드를 짜봤다. 그리고 맞았다.. 이게 진짜 이러고 나니까 시간복잡도가 확 체감이 되는 것 같다.

---

시간초과 코드 확인

# 시간초과 코드
import sys

n = int(sys.stdin.readline()) # 몇 개 를 받아올지
A = list(map(int,sys.stdin.readline().split())) # A에 list를 만들어서 저장하고
m = int(sys.stdin.readline()) # 확인할 숫자의 개수를 받아오자
B = list(map(int,sys.stdin.readline().split())) # B에 확인할 숫자를 list로 만들어 저장하고
for k in B: # B안에 있는 숫자를 확인해서 출력하자
    if k in A:
        print(1)
    else:
        print(0)

---

정답 코드 확인

import sys

n = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))

dict = {}
for i in A:
    dict[i] = 1

m = int(sys.stdin.readline())
B = list(map(int,sys.stdin.readline().split()))
for k in B:
    try:
        print(dict[k])
    except KeyError:
        print(0)