[4.16] 문제 14. 동명이인 찾기(딕셔너리)

<모두의 알고리즘 with 파이썬> 

 

문제 14. 동명이인 찾기 - 딕셔너리

 

딕셔너리

딕셔너리 dictionary : 기준이 되는 key와 value의 대응관계를 저장하는 자료 구조

* 해시 테이블 hash table : key - value를 대응시켜 자료를 보관하는 자료 구조 

#리스트 만들기
a = {}
a = dict()
#key : value
a = {"key1": "value1", "key2":"value2", "key3":"value3"}
#key 불러오기
print(a["key1"])
#새 값을 추가하기
a["key4"] = "value4"

len(a)
a[key]
a[key] = value
del a[key]
a.clear()
key in a

 

동명이인 찾는 알고리즘

 

def find_same_name(a):
  name_dict = {}
  for name in a:
    if name in name_dict:
      name_dict[name] += 1
    else:
      name_dict[name] = 1

  result = set()
  for name in name_dict:
    if name_dict[name] >= 2:
      result.add(name)

  return result

a = ["a", "b", "c", "a", "b"]
print(find_same_name(a))

* 계산 복잡도 

 

연습문제

- 학생 번호로 학생 이름을 찾는 문제를, 딕셔너리를 이용해서 풀이

- 학생 번호 입력 -> 학생 번호 이름 출력

def name(a, x):
  if x in a:
    return a[x]
  else:
    return "?"

a = {1: "a", 2:"b", 3:"c"}
print(name(a, 1))