[Python] 백준 10546번 - '배부른 마라토너' 풀이 + 해시(hash)

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

10546번: 배부른 마라토너

---

코드

import sys
N = int(sys.stdin.readline().rstrip())
mrth_dic = dict()
for _ in range(N):
    name = sys.stdin.readline().rstrip()
    if name not in mrth_dic.keys():
        mrth_dic[name] = 1
    else:
        mrth_dic[name] += 1
for _ in range(N-1):
    com = sys.stdin.readline().rstrip()
    mrth_dic[com] -= 1

for key, value in mrth_dic.items():
    if value == 1:
        print(key)
        break

 

이 문제의 카테고리를 보면, '해시를 사용한 집합과 맵' 이라는 말이 있습니다. 여기서 해시란 파이썬의 딕셔너리를 의미합니다.

 

위키백과에 따르면 '해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. ' 라고 정의 되어있는 것을 볼 수 있는데요, 임의의 길이의 데이터는 value값, 고정된 길이의 데이터는 key값이라고 볼 수 있겠네요.

 

무엇보다 해시는 무조건 정수로만 접근 가능한 리스트와는 달리 문자열 타입, 그 어떤 타입으로던 접근이 가능하다는 장점이 있습니다. 여기서 입력받는 데이터는 주로 문자열 이므로 해시를 이용하는 방법이 용이하겠습니다.

 

마라토너의 이름을 리스트에 저장해서 리스트의 인덱스값을 for문으로 반복하여 찾아내는 것 보다는 key값으로 정리하여 value값에 완주했는지 배부른 마라토너인지 알아내는 방법이 더욱 효율적이라고 볼 수 있습니다.

 

N번 입력으로 들어온 이름을 mrth_dic 딕셔너리에 key값으로 넣어두고, value값에 1을 넣었습니다. 만약 동명이인이라면 1을 더 더해주었습니다. 

 

N-1번 입력으로 들어온 완주자의 이름은 mrth_dic 딕셔너리의 해당 value값을 1씩 빼주고, 마지막까지 남아있는 한사람을 찾아내는 마지막 for문을 구현했습니다.

---

후기

처음에는 리스트를 이용하여 풀었는데 시간초과가 뜨더라고요. 그래서 찾아보니까 딕셔너리, 해시를 이용하여 푸는 방법이 더욱 효율적이라고 합니다. 그런데 이 문제는 value값을 찾는 문제인데 리스트랑 시간이 크게 다른가? 라는 의문이 들긴 합니다.