코딩테스트는 시간이 정해져 있는 시험이기 때문에, 아무래도 문제 유형을 파악하고 빠르게 해당 유형에 맞는 자료구조를 생각하는 것이 중요하기에, 상황에 알맞는 자료구조를 정리해보겠습니다.
👨 Hash
Python 에서는 dictionary를 통해 Hash를 구현할 수 있습니다.
dictionary는 삽입, 삭제, 조회가 O(1)의 시간복잡도를 가지고 확인할 수 있으므로 굉장히 빠르게 해결이 가능다하는 장점이 있습니다.
(O(1)이므로, 사실상 시간복잡도에 영향이 없다고 보셔도 무방합니다.)
그리고 Key와 Value 쌍으로 저장된다는 특징도 알아두셔야 될 것 같습니다.
따라서 검색, 삽입, 삭제를 빠르게 처리해야하고 리스트로 처리하기에는 시간복잡도 문제가 발생할 것 같은 경우에 이를 통해 해결할 수 있습니다.
추가로 검색, 삽입, 삭제가 빠르므로 응용 예제로는 특정 반복 원소의 빈도수 등을 출력하는데에 용이하게 사용될 수 있습니다.
또한 정렬이 되어 있지 않으므로 정렬이 필요한 경우에는 이에 대해 고려할 필요가 있습니다.
d1 = dict() # 빈 딕셔너리 선언
d2 = {} # 빈 딕셔너리 선언
d[k] = value # (k,v) 쌍을 추가
d.pop(k) # key가 k인 것을 찾아서 제거
k in d # 딕셔너리 d 안에 key가 k인 쌍이 있는지 여부를 확인해서 있다면 True 없다면 False를 반환참고로, pop() 등을 사용할 때, 해당 key 가 없다면 오류를 나타내기 때문에 k in d 를 항상 먼저 해주어서 오류를 방지하는 것이 좋습니다.
정렬된 딕셔너리를 사용하고 싶으면 외부 라이브러리 sortedcontainers를 이용할 수도 있습니다.
(단 코딩테스트에서는 정렬된 딕셔너리로만 풀어야하는 문제가 나오지는 않을 것이고, 실제로 사용하지 못할 확률이 큽니다.)
삽입, 삭제, 조회는 O(logN)의 시간복잡도를 가집니다.
사용법은 dict()와 거의 유사하니 참고하시길 바랍니다.
from sortedcontainers import SortedDict
sd = SortedDict() # 정렬된 딕셔너리 생성👧 HashSet
Python에는 set이라는 클래스가 존재합니다.
set이 dict와 가장 큰 차이점은 쌍으로 저장하는 것이 아니라는 것 입니다.
그래도 Hash 기반이므로 삽입, 삭제가 모두 O(1)로 이용 가능합니다.
주의할 점은 Set은 집합이므로 중복을 허용하지 않다는 것은 주의해야됩니다.
HashSet은 쌍으로 저장할 필요가 없고, 원소 유무를 비교할 경우에 유용하게 사용 가능합니다.
리스트는 특정 원소 유무를 비교해야할 때, 전부를 뒤져서 확인해야하므로 시간복잡도는 리스트 크기만큼 걸린다는 문제가 있는데, set을 사용하면, O(1)만큼 빠르게 처리가 가능합니다.
중복을 허용하지 않고, 순서를 지킬 필요가 없지만, 빠르게 삽입, 삭제, 조회가 필요한 경우에 유용하게 사용할 수 있습니다.
s1 = set() # 빈 set 생성
s.add(E) # set에 데이터 E 삽입
s.remove(E) # set에 데이터 E 삭제
E in s # set에 데이터 E 유무를 확인하고 있다면 True 없다면 False를 반환정렬된 Set을 사용하고 싶으면 외부 라이브러리 sortedcontainers를 이용할 수도 있습니다.
(단 코딩테스트에서는 정렬된 Set으로만 풀어야하는 문제가 나오지는 않을 것이고, 실제로 사용하지 못할 확률이 큽니다.)
삽입, 삭제, 조회는 O(logN)의 시간복잡도를 가집니다.
사용법은 set()와 거의 유사하니 참고하시길 바랍니다.
from sortedcontainers import SortedSet
s = SortedSet() # 정렬된 Set 생성👵 우선순위 큐
흔히 아는 FIFO 형식은 큐와는 다르게 우선순위 큐는 항상 우선순위가 높은 데이터에만 관심이 있는 자료구조입니다.
해당 자료구조를 통해서 삽입, 삭제, 조회를 O(logN) 만큼으로 해결 가능합니다.
Python에서는 PriorityQueue라는 클래스로 지원하지만 이는 매우매우매우 느리기에 이를 통해 제한시간 내에 문제를 푸는 것은 거의 불가능에 가깝다고 보시면 됩니다.
그래서 heapq를 활용해서 우선순위 큐를 이용해볼 수 있습니다.
주의할 점은 heapq는 기본적으로 max-heap이 아니라 min-heap을 구현한 것이므로 우선순위 큐를 구현하기 위해서는 원소에 -(음수)를 붙여서 이용해주고 출력할 때 다시 -를 붙이는 방법으로 약간의 꼼수(?)를 부려서 해결할 수 있습니다.
참고로, 이를 이용하기 전에 Python 에서는 빈 리스트를 만들어주어야 된다는 것을 잊지 말아주세요~!
import heapq
# 아래의 예시는 min-heap이므로 우선순위 큐로 이용하시려면 음수를 붙여주세요!!
queue = [] # 빈 리스트 생성
heapq.heappush(queue, e) # 데이터 e를 삽입
heapq.heappop(queue) # 현재 데이터 최소 값을 제거
heapq[0] # 현재 최소값을 단순 출력 (삭제 X)