[코딩테스트] 백준 수 찾기 파이썬(Python)

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

1920번: 수 찾기

성공코드에 대하여 이야기하기전에 시간초과로 실패한 코드부터 이야기하겠습니다.

 

실패코드

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

results = []
for number in numbers:
  if number in A:
    results.append(1)
  else:
    results.append(0)

for result in results:
  print(result)

주어진 numbers를 반복하면서 A안에 number가 존재하는지 판단하여 result에 결과를 저장하는 방식으로 코드를 작성하였는데

시간초과로 실패하였습니다. $O(n^{2})$의 시간복잡도가 나와서 실패한것으로 생각됩니다.

 

다음은 성공한 코드입니다.

성공코드

N = int(input())
A = list(map(int, input().split()))
M = int(input())
numbers = list(map(int, input().split()))
dic = {}
results = []
for i in A:
  dic[i] = True
for number in numbers:
  if dic.get(number):
    results.append(1)
  else:
    results.append(0)

for result in results:
  print(result)

시간복잡도를 줄이기 위하여 딕셔너리 구조를 이용하여 A에 있는 모든 숫자들을 딕셔너리에 저장하였습니다.

그리고 numbers를 반복하면서 dic.get(number)를 하면 주어진 number가 딕셔너리에 있는지 확인하게 됩니다.

실패한코드와 차이점은 실패한 코드에서는 number in A로 $O(n)$의 시간복잡도가 걸리지만 dic.get()함수는 $O(1)$의 시간복잡도가 걸리게 됩니다. 여기서 시간복잡도를 줄여 문제를 해결할 수 있었습니다.