TIL - algorithm - 해시

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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"

풀이

• 처음엔 for loop를 활용해서 completion 배열의 요소 중, participant 배열에 존재하는 요소를 모두 제거하여 최종적으로 남은 요소를 답으로 return 하는 방법을 생각했다. 하지만 이 단순한 방법엔 시간 복잡도가 엄청나게 증가한다는 단점이 존재했다.(시간 복잡도가 최대 O(N^2)에 가까워진다.)

• 결국 배열 이외의 자료구조를 활용하는 게 이 문제의 핵심이다. 다양한 자료구조가 있지만 key값을 통해 value에 빠르게 접근할 수 있어서 자료 탐색 속도가 빠른 해시를 이용했다. 우선 해시 구조로 바꿀 배열로 participant를 선택했다. 이유는 participant의 요소(key, value) 중 completion에 존재하지 않는 값이 있다면, 그 값을 완주하지 못한 선수로 특정할 수 있기 때문이다.

• 우선 participant의 요소를 key로, 요소의 개수를 value로 하는 해시 자료 구조 participant_dict를 생성했다. 이름이 중복될 수 있으므로, key값이 같은 경우 개수를 1씩 늘려줬다.

def solution(participant, completion):
    participant_dict = {}
    for key in participant:
        if participant_dict.get(key):
            participant_dict[key] += 1
        else:
            participant_dict.setdefault(key, 1)
    return answer

• 이제 참가자 명단(participant_dict)에서 완주 명단(completion)에 존재하지 않는 사람을 소거해주자. 소거라고 해서 값을 삭제하지는 않고, value값을 1씩 감소시키는 것으로 대신했다.

def solution(participant, completion):
    participant_dict = {}
    for key in participant:
        if participant_dict.get(key):
            participant_dict[key] += 1
        else:
            participant_dict.setdefault(key, 1)
    
    for person in completion:
        if participant_dict.get(person):
            participant_dict[person] -= 1
            
    return answer

• 이제 참가자 명단(participant_dict)에서 완주한 사람(key)의 value 는 0이 됐을 것이고, 완주하지 못한 사람의 value는 1이 됐을 것이다. 여기서 value가 1인 key 값을 찾아주면 된다. 찾는 방법은 간단하다. 기존 해지 자료 구조를 뒤집으면 된다.

def solution(participant, completion):
    participant_dict = {}
    for key in participant:
        if participant_dict.get(key):
            participant_dict[key] += 1
        else:
            participant_dict.setdefault(key, 1)
    
    for person in completion:
        if participant_dict.get(person):
            participant_dict[person] -= 1

    reversed_dict = dict(map(reversed, participant_dict.items()))
    answer = reversed_dict[1]

    return answer

다른 풀이

def solution(participant, completion):
    answer = []
    completion_dict = {}
    
    for person in completion:
        if completion_dict.get(person):
            completion_dict[person] += 1
        else:
            completion_dict[person] = 1
        
    for s in participant:
        if not completion_dict.get(s):
            answer.append(s)

        else:
            if completion_dict.get(s) ==0:
                answer.append(s)
            else: 
                completion_dict[s] -= 1
    return answer[-1]