[백준 10815 파이썬] 숫자 카드 (실버 4, 집합)

알고리즘 유형 : 집합
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
inven = set(map(int, input().split()))
M = int(input())
for i in map(int, input().split()):
    if i in inven:
        print(1, end=" ")
    else:
        print(0, end=" ")

풀이 요약

1. 입력받은 카드 셋을 set 형으로 저장한 후, 찾고자 하는 카드 셋을 순회하면서 집합에 들어있는지를 검사한다.

2. 이 때 숫자가 카드 셋에 들어있는지 검사할 때의 시간복잡도는 O(1)이다.

   그 이유는 set이 내부적으로 hash를 사용하는 자료구조이기 때문이다.

   set에는 값 자체를 바로 저장하는게 아니라, hash function를 거쳐 hash 값으로 변환 후 저장한다. 이 때 원래의 값과 hash는 key-value의 구조를 가지기에, 탐색의 시간복잡도가 O(1)인 것이다.

   참고로, 삽입과 삭제도 O(1)이다. 다만, 삽입은 어떤 값을 해시로 변환했을 때 해시테이블에 그 값이 이미 들어있을 수도 있으므로, 충돌 여부 검사를 거쳐 O(N)까지 걸릴 수 있지만, 파이썬에서는 내부적으로 이러한 해시 충돌을 커버해주는 코드가 있으므로 삽입도 O(1)로 수행가능하다고 한다.

배운 점, 어려웠던 점

• set 자료구조에 대해 좀 더 자세히 알 게 됐다.