[프로그래머스] - 완주하지 못한 선수

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

사실 해시 관련 문제가 어떤 것인지 잘 몰랐는데, 이 문제를 풀면서 대략적인 방법을 알게 된 것 같다.

해시 관련 문제를 풀 때는 어떻게 하면 탐색을 O(1)에 할 수 있는지를 생각하는게 중요하다 생각했다.

파이썬에서는 다행히 딕셔너리라는 좋은 자료형을 제공해줘서 딕셔너리를 잘 이용하면 될 것 같다.

 

이 문제는 완주자의 수가 (참여자의 수 - 1)이므로 사실상 같다고 할 수 있다. 따라서 참여자의 수를 n이라고 하면 1 <= n <= 100000이므로 시간복잡도를 최대 O(nlogn)까지 가능할 것이라 파악했다.

이 문제에서는 참여자 중 완주자에 포함되지 않는 사람을 찾는 것이고, 이를 위해 완주자가 참여자에 있는지 탐색을 하였다.

이 때, 탐색을 O(1)에 하기 위해 딕셔너리를 이용했고, 중복된 이름의 참여자가 있을 수 있으므로 딕셔너리의 Key로는 참여자의 이름, Value로는 Key값을 이름으로 가진 사람의 수를 저장하였다.

그리고 각 완주자들에 대해서 해당 완주자가 있으면 딕셔너리의 Value값을 1씩 감소시키고, Value가 0이 되면 Key를 이름으로 가진 사람은 완주를 했다는 것이므로 딕셔너리에서 삭제한다.

이러한 과정을 거치면 최종적으로 딕셔너리의 Key로는 완주하지 못한 한 사람의 이름과, Value값으로는 1을 갖게 된다.

따라서 하나 남은 Key를 최종 답으로 제출하면 된다.

 

해당 풀이는 O(n) 시간복잡도를 갖는다.

def solution(participant, completion):
    answer = ''
    participant_dict = {}
    
    for p in participant:
        if p not in participant_dict:
            participant_dict[p] = 1
        else:
            participant_dict[p] += 1
    
    for c in completion:
        participant_dict[c] -= 1
        if participant_dict[c] == 0:
            del participant_dict[c]
    
    answer = list(participant_dict.keys())[0]
    
    return answer

 

해당 알고리즘의 채점 결과이다.

 

그리고 defaultdict를 사용하면 key값에 대해서 if Key not in dict 구문을 사용하지 않아도 되므로 코드를 약간 간결하게 할 수 있다. 다만 시간은 기본 dictionary를 사용했을 때 보다 조금 느리다.

from collections import defaultdict

def solution(participant, completion):
    answer = ''
    participant_dict = defaultdict(int)
    
    for p in participant:
        participant_dict[p] += 1
    
    for c in completion:
        participant_dict[c] -= 1
        if participant_dict[c] == 0:
            del participant_dict[c]
    
    answer = list(participant_dict.keys())[0]
    
    return answer