[사전/dict]

해시 테이블은 key-value로 저장하는 자료구조이다.
그렇게 따지면 리스트도 인덱스-내용 아니냐? 하겠지만 많이 다르다.
해시 테이블은 탐색이 $O(1)$인 탐색 능력이 특화된 자료구조이다.
리스트에서 특정 데이터를 찾으려면 순차탐색이므로 $O(n)$이다.

(C++의 map은 Red-Black Tree로 구현하여 $O(\log{n})$이라 한다.)

python에서는 dict 객체를 제공한다.
간단하게 D[key] = value로 생각하면 쉽다.

빈 사전은 다음과 같이 초기화환다.

# empty dictionary
D1 = {} 
D2 = dict()

데이터의 추가, 삭제는 다음과 같다

D[key] = value   # {key:value}가 사전에 추가
del D[key]       # {key:value}가 사전에서 삭제

데이터의 접근방법은 다음과 같다

a = D[key] # a는 {key:value}의 value가 저장
b = D.get(x)  # D[x]와 동일한 결과값
              
# x가 존재하지 않을 경우, D.get(x)는 None을 반환 # D[x]는 오류


# 딕셔너리 값을 증가, 없으면 1로 초기화
# 아래처럼 하면 길다....
if x in D:
    D[x] = 1
else:
    D[x] += 1
    
D[x] = D.get(x, 0) + 1 # D[x]가 없으면 0으로 한다. 즉, 자동으로 D[x]값 증가

예제. 완주하지 못한 선수
해설) participant는 참가자 이름이 있는 리스트, completion는 완주자 이름이 있는 리스트이다. 항상 completion은 participant보다 1 적고 동명이인이 있을 수 있다.
D = dict() 하나를 생성하여 participant가 들어올때마다 1씩 증가.
completion이 들어올때마다 1 삭제. 만약 D[name] = 0이라면 해당 name을 갖는 이름은 모두 완주했으므로 데이터 삭제한다.

D = dict() # empty dictionary

# 참가자 데이터 저장
for p in participant:
    if p in D:
        D[p] += 1  # 이미 동명이인이 있다면 1 추가
    else:
        D[p] = 1   # 처음 보는 참가자

# 참가자에서 완주자 데이터 제거
for c in completion:
    D[c] -= 1 # 완주자 데이터 제거
    if D[c] == 0: # 같은 이름의 참가자가 없다면
        del D[c]  # 해당 데이터 삭제

# 이제 D에는 하나의 데이터만 존재한다
# D.keys()는 1개의 데이터만 존재
# list()로 만들어서 0번째 index를 참조
return list(D.keys())[0]

유제1. BOJ 1620: 나는야 포켓몬 마스터 이다솜
문제가 쓸데없이 길다.

1. (포켓몬이름 : 포켓몬숫자)의 쌍으로 저장
2. 이름이 들어오면 숫자를 답한다.
3. 숫자가 들어오면 이름을 답한다.

해시로 이루어진 자료구조는 key가 들어왔을 때 value를 찾을 수 있지만, value로 key를 찾을 수 없다. 해시함수의 역함수가 존재하지 않기 때문이다. 그러므로 value-key를 찾을수 있는 별도의 자료구조가 필요한데 value가 순차적인 순자이므로 list가 적절하다.

# 아래 주석을 사용하면 입출력 시간을 단축시킬 수 있다.
#import sys
#input = sys.stdin.readline

N, M = map(int, input().split())
D = dict()
L = [0]
for i in range(1, N + 1):
    name = input().rstrip()
    D[name] = i
    L.append(name)


for _ in range(M):
    data = input().rstrip()
    # 이름이라면 dict에서 숫자를 찾는다.
    if data.isalpha():
        print(D[data])
    # 숫자라면 list에서 이름을 찾는다
    elif data.isdigit():
        print(L[int(data)])

유제2. BOJ 17219 비밀번호찾기
포켓몬 문제와 같이 value로 key를 찾을 수 없으므로 별도의 list를 만들어서 해결한다.

유제3. BOJ 1302 베스트셀러
key로 책의 이름, value로 팔린 횟수로 한다.
value가 최대인 key를 리스트에 넣어 해결한다.

N = int(input())
D = dict()
for _ in range(N):
    book = input()
    if book in D.keys():
        D[book] += 1
    else:
        D[book] = 1
L = []
maxCount = -1
for k, v in D.items():
    if v > maxCount:
        L.clear()
        L.append(k)
        maxCount = v
    elif v == maxCount:
        L.append(k)
L.sort()
print(L[0])

해시 자료구조 문제 특징을 정리해보았다.

1. 탐색이 주된 알고리즘이라면 해시를 이용한 자료구조를 선택한다.
2. 해시의 역연산(value로 key찾기)에 대한 해결방안
   2.1 value가 연속적이라면 배열을 이용
   2.2 value가 이산적이라면 또다른 딕셔너리로 이용