-
백준 10546 - 배부른 마라토너BOJ-Algorithm 2022. 1. 21. 10:16
https://www.acmicpc.net/problem/10546
10546번: 배부른 마라토너
마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명
www.acmicpc.net
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
'BOJ-Algorithm' 카테고리의 다른 글
백준 4673 - 셀프 넘버 (0) 2022.01.28 백준 9414 - 프로그래밍 대회 전용 부지 (0) 2022.01.22 백준 7785 - 회사에 있는 사람 (0) 2022.01.20 백준 11728 - 배열 합치기 (0) 2022.01.19 백준 16120 - PPAP (0) 2022.01.18