[파이썬/알고리즘] 프로그래머스 - 완주하지 못한 선수 (Hash)

[문제]

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

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

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

 

[풀이]

def solution(participant, completion):
    hashDict = {}
    hashSum = 0
    
    for i in participant:
        hashDict[hash(i)] = i
        hashSum += hash(i)
        
    for j in completion:
        hashSum -= hash(j)
    
    return hashDict[hashSum]

 

Hash는 딕셔너리 형태와 마찬가지로 Key : Value로 구성되어 있으며 Hash를 이용하여 해당 문제를 풀었다.

먼저 hashDict = {} 으로 Hash 구조를 선언하고, hashSum = 0 으로 선언한다.

hashSum을 선언 한 이유는 뒤에서 알 수 있다.

 

첫 번째 for문을 통해서 참여자에 대해서 hash로 저장이 된다.

예를 들어, 참가자가 ['A', 'B', 'C'] 이렇게 있으면 A, B, C는 Value로 들어가고 Key는 Hash를 통해 값이 생성된다.

Hash 값(숫자)이 몇으로 생성되는지는 Hash 함수로 고유의 값을 가지게 되고 어떤 값이 가지는지 궁금하다면

파이썬에서 'print(hash('A')) 를 해보면 A에 해당하는 값이 얼마인지 볼 수 있다.

 

예를 들어, 첫 번째 반복문을 돌면서 A가 42, B가 34, C가 7 이라는 값을 가지게 되면

hashSum += hash(i)를 통해서 값이 누적돼서 42 + 34 + 7로 83의 값을 가지게 된다.

 

그리고 Completion에 ['A', 'B'] 이렇게 있다고 가정하면, 두 번째 반복문을 돌면서 누적으로 빼주게 된다.

A에 해당하는 42를 빼주고, 다음은 B에 해당하는 34를 빼준다. 그럼 남은 값은 7이 된다.

 

최종적으로 7에 대한 값을 HashDict에서 불러오면 참가자 중에 완수하지 못 한 선수가 나오게 된다.