완주하지 못한 선수

문제 설명

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

제한사항

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

처음 생각한 풀이

"participant를 다 조사해서 completion에 없는 사람을 찾아내면 되는 것 아니야?" 하는 생각이 제일 먼저 들었다. 때문에 다음과 같은 코드를 생각했었다.

def solution(participant, completion):
    for i in range(len(participant)):
        for j in range(len(completion)):
            if participant[i] == completion[j]:
                break
            if j == len(completion) - 1:
                return participant[i]
    return participant[len(completion) - 1]

하지만 딱보기에도 for문을 2번 돌아야 하기 때문에 O(n^2)의 시간 복잡도로 시간 초과가 발생할 것이라고 생각해서 해당 코드는 폐기했다. (채점을 다 끝나고 해당 코드도 테스트해보았더니 예상대로 시간 초과였고, 5번 케이스에서는 정답도 틀렸다.)

그 다음 생각한 방법은 set이었다. Python의 set을 이용해서 차집합을 구하면 participant에는 있는데 completion에는 없는 선수를 구할 수 있을거라고 생각했다.

하지만 이 방법에는 결정적인 문제가 있었는데, 바로 "참가자 중에는 동명이인이 있을 수 있습니다." 라는 조건이었다. 주어진 list들을 set으로 만들면, set은 중복을 허용하지 않기 때문에 participant에 있는 동명이인들이 없어지게 되어 답이 틀리게 된다.

때문에 다른 방법을 찾아보던 도중, 문제의 카테고리가 해시였기 때문에 해시를 사용하는 방법을 찾았다. 문제에 힌트가 있었다. 바로 "completion의 길이는 participant의 길이보다 1 작습니다." 라는 조건이었다. participant가 completion보다 딱 한 명 더 많기 때문에, 모든 participant의 요소들의 해시값을 다 더해서, 모든 completion의 요소들의 해시값을 빼주면 완주하지 못한 선수의 해시값만 남는다.

관건은 마지막 남은 해시 값을 가지고 선수의 이름을 찾는 방법이었고, 이 부분은 dictionary를 사용했다. Python의 dictionary는 key와 value를 쌍으로 하는 순서가 없는 집합 자료구조다. 때문에 key를 해시 값으로, value를 이름으로 설정해주면 마지막 남은 해시 값을 통해 dictionary에 접근하여 이름을 찾을 수 있다.

코드는 다음과 같다.

def solution(participant, completion):
    d = dict()
    hashValue = 0
    for p in participant:
        d[hash(p)] = p
        hashValue += hash(p)
    for c in completion:
        hashValue -= hash(c)
    return d[hashValue]

테스트 결과 모든 테스트를 정상적으로 통과했다.

다른 풀이

프로그래머스의 다른 풀이를 보던 도중, 가장 많은 좋아요를 받은 풀이가 굉장히 신기했다. 바로 collections 모듈을 사용하는 방법이었다. collections 모듈의 Counter 클래스는 dictionary를 확장한 클래스로, 데이터의 개수를 효과적으로 셀 수 있는 기능을 제공한다.

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

여기서는 Counter 객체 끼리 뺄셈이 가능하다는 점을 이용했다. Counter(participant)는 participant의 각 요소들과 그 개수를 짝지어서 가지고 있기 때문에, Counter(completion)을 빼 주게 되면 겹치는 요소들의 개수를 빼서 결과적으로 answer에는 단 하나의 이름(key)과 1(value)만 남게 된다. 따라서 answer.keys()를 list로 만들어 주면 0번째 인덱스가 완주하지 못한 선수의 이름이다.