백준 10546 - 배부른 마라토너

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

10546번: 배부른 마라토너

import sys

input = sys.stdin.readline

arr = dict()
n = int(input().strip())
for i in range(n):
    name = input().strip()
    if name in arr.keys():
        arr[name]+=1
    else:
        arr[name]=1
for j in range(n-1):
    name = input().strip()
    arr[name]-=1
print(list(arr.keys())[list(arr.values()).index(max(list(arr.values())))])

해시 테이블을 활용하는 문제긴 한데, 동명이인이 있을 수 있다고 한다. 그러면 set은 사용할 수 없다. list로 제출하면 시간초과가 뜬다. 파이썬에서는 해시테이블을 제공해주는 자료구조가 set말고도 dict가 있다. 이번 문제는 dict로 푸는 것이 좋다.

 

참가자들의 이름을 입력받고, 동명이인인 경우에는 arr[name]에 +1을 해서 동명이인이 있다는 것을 표시한다.

 

완주자들의 이름을 입력받을 때마다, arr[name]에 -1을 해 둔다.

 

문제의 조건에서, 완주를 하지 못한 사람은 단 1명이므로 dict의 value 값은 아마 0,0,0,1,0,0,0.... 이 될 것이다.

이 중 1인 것의 인덱스를 찾고, 해당 값의 인덱스에 해당하는 dict의 key값을 찾아 출력한다.

이 부분은 stackoverflow의 도움을 받았다.

참고 : https://stackoverflow.com/questions/268272/getting-key-with-maximum-value-in-dictionary