[Programmers] 해시 - 완주하지 못한 선수

오늘은 프로그래머스의 알고리즘 고득점 Kit의 가장 첫 번째 쉬운 문제인 완주하지 못한 선수 문제를 풀어보았다.
파이썬으로 문제를 푼다면, 해시 카테고리의 문제들은 딕셔너리로 풀 수 있는데, 해시(hash)의 가장 큰 장점은 배열 혹은 리스트와 다르게 자료의 검색 및 접근에 있어서 시간 복잡도가 O(1)로 매우 빠르게 동작한다는 것이다.
 
오랜만에 코딩을 하다 보니 처음에는 사람 수를 초기화하기 위해서 첫 번째 for문 안에서 dict[i] = participant.count(i)를 사용하였는데 이 경우, 결국 초기에 participant를 순회하는 과정과 더불어 한 번 더 리스트 안에서 검색을 하기 때문에 O(N^2)의 시간 복잡도가 필요하여 시간 초과로 실패한다.
 
결국 코드가 조금 길어지더라도 정석적인 풀이를 진행하였고, 문제가 풀렸다.
 
먼저 전체 참가자의 수를 딕셔너리 안에 초기화한다. 동명이인이 있다고 하였으니 모두 1로 초기화하면 안 된다.
not in을 사용하여 키로 사용할 이름이 딕셔너리에 존재하지 않으면 1로 초기화하고, 이미 있다면 동명이인이므로 1을 더해준다.

# 1. 참가자 명단을 돌며 딕셔너리에 빈도수 카운트 (O(1) 접근)
    for i in participant:
        if i not in dict:
            dict[i] = 1
        else:
            dict[i] += 1

 
다음으로 completion에는 완주자 명단이 있다고 하였으니 완주자 명단을 하나씩 불러와서 딕셔너리에 키로 넣어 하나씩 값을 감소시킨다.
이때, 처음에는 습관적으로 "if를 사용해서 같으면 뺄까?" 라는 생각도 하였으나 이미 완주를 했다는 것은 무조건 참가자라는 것이기 때문에 불필요한 과정이라 삭제하였다.

# 2. 완주자 명단을 돌며 딕셔너리에서 값 차감
    for i in completion:
        dict[i] -= 1

 
문제 조건을 읽어 보면 "completion의 길이는 participant의 길이보다 1 작습니다."라고 명시되어 있으므로, 완주하지 못한 선수는 1명만 존재한다는 것을 알 수 있다. 즉, 위에서 작성한 알고리즘대로 코드가 진행되었을 때, 최종적으로 value가 1인 key가 완주하지 못한 선수라는 것을 알 수 있다.
따라서 items() 메소드를 사용하여 value가 1인 key를 답으로 반환하면 정답을 찾을 수 있다.

# 3. 값이 1인 완주하지 못한 선수 찾기
    for k, v in dict.items():
        if v == 1:
            answer = k

 
전체 코드

def solution(participant, completion):
    answer = ""
    dict = {}
    for i in participant:
        if i not in dict:
            dict[i] = 1
        else:
            dict[i] += 1
    
    for i in completion:
        dict[i] -= 1
    for k, v in dict.items():
        if v == 1:
            answer = k
    return answer