문제

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1

"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2

"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3

"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

풀이과정

---

해당 문제는 해시를 사용해서 풀 수도 있고, for문 루프를 통해 해결할 수도 있다. 나는 participant 의 복제 배열을 하나 생성하고 for문을 통해 participant와 completion에 둘 다 있는 값을 빼고 남은 값을 반환하는 방식으로 문제를 해결하려 했지만 효율성 테스트에서 0점을 맞고 말았다.

이 문제를 python 에 있는 해시 구조인 dictionary를 통해 풀었다.

먼저 Participant의 정보로 hash table을 만들면 아래와 같이 된다.

Key	Value
17	leo
5	iden
12	kiki

이 때 hashSum 을 통해 participant 의 Key값을 전부 합친다.

Completion에는 participant의 해시 테이블과 동일한 value를 갖기 때문에 key 값도 동일하다. 그렇기에 completion으로 for문을 돌려 더해진 hashSum 만큼 completion의 이름 값으로 빼준다면 key값이 남을 것이고, 해당 key값으로 value를 찾을 수 있다.

정답 코드는 아래와 같다.

def solution(participant, completion):
    answer = ''
    hashDict = {} #딕셔너리 해시 생성
    hashSum = 0
    for part in participant:
        hashDict[hash(part)] = part
        hashSum += hash(part)
    for comp in completion:
        hashSum -= hash(comp)
    
    answer = hashDict[hashSum]
    
    return answer

코드 분석

이 코드에서 내가 보기에 핵심은 hashSum이다. hash() 를 통해 문자열에 고유한 해쉬 번호를 생성하여 hashSum에 더하고, 또 (하나를 제외한) 동일한 문자열로 hash()를 생성하여 completion에 없는 hash번호를 key로 찾아 마지막 이름을 찾는 것이다.