10546번 - 배부른 마라토너

1. 배부른 마라토너

• 난이도
  • 실버 4
• 시간 제한
  • 1초
• 메모리 제한
  • 256 MB
• 출처
  • 10546번: 배부른 마라토너 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😊 1차 시도 (성공)

import sys  
  
input = sys.stdin.readline  
  
n = int(input())  
  
participants = {}  
p_hash = 0  
  
for _ in range(n):  
    temp = input()  
  
    participants[hash(temp)] = temp  
    p_hash += hash(temp)  
  
for _ in range(n-1):  
    temp = input()  
  
    p_hash -= hash(temp)  
  
print(participants[p_hash])

a. 🙄 회고

내 풀이

• 해시 함수를 통해 key를 만들고, dict 자료형에 해시 함수 값을 key - 이름을 value로 매핑하여 해결하였다.
• 해시 함수를 통해 만든 key 값을 계속 더하고 완주자는 빼는 방식으로 풀면 완주하지 않은 한 명을 구할 수 있다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

hash()를 통해 이름에 매핑되는 고유의 키값을 구할 수 있다.

구한 키값은 이름과 매핑시켜 dict 자료형으로 만든다.

참가자들의 hash함수 결과 (key 값들)을 모두 더하고, 완주자를 모두 뺀다.

그럼 만들어지는 수가 완주하지 않은 사람이 된다.

해당 key 값을 dict에서 탐색하면 완주하지 않은 사람의 이름을 구할 수 있다.

이 방식은 동명이인이 있더라도 동일하게 적용할 수 있다.

다만, 완주자가 1명 이상일 경우에는 이 방법으로 해결할 수 없다.

참고문헌

baekjoon. 10546번: 배부른 마라토너 (acmicpc.net). Baekjoon. (accessed Dec 28, 2021)