[자료 구조] 동명이인 찾기 / 딕셔너리

딕셔너리(dictionary, 사전)

정보를 찾는 기준이 되는 키(key)와 키에 연결된 값(value)의 대응 관계를 저장하는 자료 구조

key-value 형태의 자료구조를 해시 테이블(Hash Table)이라고 하며, 프로그래밍 언어마다 다르게 불릴 수 있다.

C++에서는 unordered_map, Java에선 haspmap이라고 부른다.

 

코드

# 빈 딕셔너리 선언
d = {}
d = dict()

# 선언과 동시에 초기화
d = {
    KEY1: VALUE1, # 키와 값은 콜론으로 구분
    KEY2: VALUE2, # 키와 키는 쉼표로 구분
    KEY3: VALUE3, 
    KEY4: VALUE4
}

# d 자료 개수 확인
len(d)

# 값 찾기
d[KEY]

# 값 추가. 키 중복 미허용. 기존 값이 있는 경우 overwrite
d[KEY] = VALUE

# 값 삭제
del d[KEY]

# 딕셔너리 초기화
d.clear()

# 키 값 존재 여부 확인
KEY in d # 존재하면 True
KEY not in d # 존재하지 않으면 True

 

동명이인 찾기

입력으로 받은 목록을 탐색하며 이름을 키로, 이름이 등장한 횟수를 값으로 하여 딕셔너리에 저장한다.

탐색이 끝나면 딕셔너리 내 값이 2 이상인 이름을 집합에 저장하여 반환한다.

def same_name(list):
    d = dict()
    s = set()

    for name in list:
        if name in d:
            d[name] += 1
        else:
            d[name] = 1

    for name in d:
        if d[name] > 1:
            s.add(name)

    return s

계산 복잡도는 \( \mbox{O}(n) \)이다.