완주하지 못한 선수 (Programmers 12930)

🧑‍💻 문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다.
단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

🧑‍💻 해결방법

이 문제의 카테고리는 애초에 '해시' 알고리즘 이었다.
파이썬으로 해시 알고리즘을 해결하기 위해서는 딕셔너리에 대한 이해가 필요하다.

🧑‍💻 Hash algorithm?

• key 값과 value 값을 활용하여 탐색의 횟수를 줄여준다.
• 쉽게 생각해보면 배열에서 index로 탐색하는 방법과 유사하게 이해하면 된다.

🧑‍💻 코드

def solution(participant, completion) :
    dic = {}
    for value in participant :
    	# get(value, 0) + 1
        # get 함수는 key 값으로 value를 얻어낼 수 있다.
        # 해당 딕셔너리에 value가 없을시 0
        # 처음에 1을 대입하여 주고 같은 값이 나타나면 +1
        dic[value] = dic.get(value, 0) + 1
    for value in completion :
    	# completion 리스트에 같은 값이 있으면 해당 딕셔너리에서 -1
        dic[value] -= 1
    
    # value를 i, key를 j
    # items() 함수는 딕셔너리의 값을 가져온다. (key와 value)
    sol = [i for i, j in dic.items() if j > 0]
    
    answer = sol[0]
    return answer

🧑‍💻 총평

알고리즘 공부를 다시 시작하면서 들어보기만 했던 hash algorithm이다.
오랜만에 새로운 것을 익히게 되어 신나면서도 두려움이 생겨났던 문제다.
하지만 언제나 그렇듯 빨리 알고싶어하면 빠르게 잊혀지며, 천천히 뜯어봐야 오래 남는 법이다.
딕셔너리의 사용법도 익힐 수 있게되어 좋은 문제 풀이였다.