5월1일 - [Python] list와 set에서의 데이터 찾기 차이 - 배열과 해시 테이블

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

1920번: 수 찾기

위 문제를 풀면서 나는 이진 탐색을 통해 문제를 해결했지만

간단하게 자료구조와 if not in 커맨드를 통해 해결하는 방법도 있어서 공부를 하던 중

 

N = int(input())
arr = list(map(int, input().split()))
M = int(input())
target_arr = list(map(int, input().split()))

for target in target_arr:
  if target not in arr:
    print(0)
  else:
    print(1)

N = int(input())
arr = set(map(int, input().split()))
M = int(input())
target_arr = list(map(int, input().split()))

for target in target_arr:
  if target not in arr:
    print(0)
  else:
    print(1)

위 두 코드가 결과의 차이가 있다는 것을 알게 되었다.

입력값에 대해 위는 list로 받고, 아래는 set으로 받는 차이가 있는데

if target not in arr을 할 때 해당 자료구조들에서 특정 값을 찾을 때 발생하는 시간의 차이가 나기 때문에

정답 결과에 차이가 있는 것이었다.

 

list와 set은 자료구조가 다르다.

일반적으로 list는 배열이고, set은 중복을 허용하지 않는 배열 정도로만 간단하게 이해하고 있었는데

 

정확하게 말하자면, list는 자료구조 중 배열에 해당하고

set은 해시 테이블에 해당한다.

 

배열에서 특정 값의 존재 여부를 확인하려면 배열은 원소를 하나씩 차례대로 확인해야 되기 때문에

시간복잡도는 O(N)이다. 

 

해시 테이블은 특정 값을 찾을 때 최악의 경우 O(N)의 시간복잡도가 발생할 수 있지만

대체로 O(1)의 시간복잡도가 걸리기 때문에 list보다는 set이 보다 빠르게 원소의 존재 여부를 확인할 수 있는 것이다.

 

때문에 문제의 결과도 차이가 발생하는 것이며, set을 사용했을 때 시간초과 없이 통과될 수 있었던 이유가 된다.