Logo

완주하지 못한 선수

프로그래머스의 완주하지 못한 선수 문제를 함께 풀어보도록 하겠습니다.

문제

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

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

예제

Input:
  participant = ["leo", "kiki", "eden"],
  completion = ["eden", "kiki"]
Output: "leo"
Input:
  participant = ["marina", "josipa", "nikola", "vinko", "filipa"],
  completion = ["josipa", "filipa", "marina", "nikola"]
Output: "vinko"
Input:
  participant = ["mislav", "stanko", "mislav", "ana"],
  completion = ["stanko", "ana", "mislav"]
Output: "mislav"

풀이 1

입력 데이터에 중복이 있는 경우에는 정렬을 해놓으면 다루기가 수월해지는 경우가 많은데요. 마지막 예제의 참가자 배열과 완주자 배열을 한 번 정렬해보면 다음과 같은 모습이 됩니다.

participant = ["ana", "mislav", "mislav", "stanko"],
completion = ["ana", "mislav", "stanko"]

자, 이제 두 배열을 동시에 루프돌면서 각 선수를 비교하다가 틀린 경우가 나오면 해당 선수가 완주하지 못했다는 것을 쉡게 알 수 있겠죠?

participant = ["ana", "mislav", "mislav", "stanko"],
                 ✅       ✅       ❌
completion = ["ana", "mislav", "stanko"]
                ✅       ✅

이 정렬을 사용한 알고리즘을 코드로 구현해보겠습니다.

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    return participant[-1]

이 풀이는 정렬을 사용하므로 시간 복잡도가 O(n log n)이 되고요. 공간 복잡도는 입력 배열 외에는 별도의 메모리를 사용하지 않으므로 O(1)입니다.

풀이 2

모든 완주자의 수는 모든 참가지의 수보다 1이 작으므로, 모든 참가자에서 모든 완주를 빼면 딱 한명이 남을 것입니다. 그런데 단순히 선수의 이름만 고려하는 것으로는 부족할 수 있습니다.

예를 들어, 마지막 예제에서는 "mislav"라는 선수가 2명 참가했고, 그 중 한 명만 완주했기 때문에 남은 한 명이 완주하지 못한 선수가 됩니다. 따라서 각 이름의 선수가 몇 명 참가했는지도 파악을 해야 정확한 결과를 얻을 수 있습니다.

그럼 마지막 예제를 기준으로 각 참가자의 수를 세어 해시 테이블에 저장해보게습니다.

participant = ["mislav", "stanko", "mislav", "ana"]

{
  "mislav": 2,
  "stanko": 1,
  "ana": 1
}

그 다음 왼주자 배열을 루프 돌면서 각 선수를 한 명씩 빼줍니다. 루프를 다 돌았는데 아직 남아잇는 마지막 한 선수가 완주를 못한 선수일 것입니다.

completion = ["stanko", "ana", "mislav"]
                 👆

{
  "mislav": 2,
  "stanko": 1 - 1 = 0,
  "ana": 1
}
completion = ["stanko", "ana", "mislav"]
                          👆

{
  "mislav": 2,
  "stanko": 0,
  "ana": 1 - 1 = 0
}
completion = ["stanko", "ana", "mislav"]
                                  👆

{
  "mislav": 2 - 1 = 1, 👈 혼자 남음
  "stanko": 0,
  "ana": 0
}

이 해시 테이블을 활용한 알고리즘을 코드로 구현해볼까요?

def solution(participant, completion):
    counter = {}
    for comp in participant:
        counter[comp] = counter.get(comp, 0) + 1
    for comp in completion:
        if comp in counter:
            counter[comp] -= 1
        if counter[comp] == 0:
            del counter[comp]
    return list(counter.keys())[0]

이 풀이는 해시 테이블에 모든 완주자의 수를 저장하므로 공간 복잡도가 O(n)으로 저하가 되는데요. 대신에 정렬을 사용하지 않고, 단순히 완주자 배열과 참가자 배열을 순차적으로 루프를 돌므로 시간 복잡도는 O(n)으로 향상이 됩니다.

참고로 위 코드는 파이썬의 내장된 자료구조인 Counter를 사용하면 다음과 같이 간소화할 수도 있습니다. 면접관에게 파이썬에 익숙하지 않은 경우 Counter에 대해서 설명을 해야되서 오히려 득보다 해가 될 수도 있으므로 대면으로 진행되는 코딩 시험에서는 그닥 추천드리지는 않겠습니다.

from collections import Counter

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

풀이 3

두 번째 풀이에서는 참가자 수에서 완주자의 수를 뺐었는데요. 이번에는 반대로 완주자의 수에서 참가자의 수를 빼보면 어떨까요?

그럼 마지막 예제를 기준으로 각 완주자의 수를 세어 해시 테이블에 저장해보게습니다.

completion = ["stanko", "ana", "mislav"]

{
  "stanko": 1,
  "ana": 1
  "mislav": 1,
}

그 다음 참가자 배열을 루프 돌면서 각 선수를 한 명씩 빼줍니다. 더 이상 뺄 수 없는 선수, 즉 0명인 선수를 만난다면, 그 선수는 완주하지 못했다는 뜻입니다.

participant = ["mislav", "stanko", "mislav", "ana"]
                  👆

{
  "stanko": 1,
  "ana": 1
  "mislav": 1 - 1 = 0,
}
participant = ["mislav", "stanko", "mislav", "ana"]
                            👆

{
  "stanko": 1 - 1 = 0,
  "ana": 1
  "mislav": 0,
}
participant = ["mislav", "stanko", "mislav", "ana"]
                                      👆

{
  "stanko": 0,
  "ana": 1
  "mislav": 0, ❌ 뺄 수 없음
}

이 해시 테이블을 활용한 알고리즘을 코드로 구현해볼까요?

def solution(participant, completion):
    counter = {}
    for comp in completion:
        if comp in counter:
            counter[comp] += 1
        else:
            counter[comp] = 1
    for part in participant:
        if part in counter and counter[part] > 0:
            counter[part] -= 1
        else:
            return part

이 풀이는 해시 테이블에 모든 완주자의 수를 저장하므로 공간 복잡도가 O(n)으로 저하가 되는데요. 대신에 정렬을 사용하지 않고, 단순히 완주자 배열과 참가자 배열을 순차적으로 루프를 돌므로 시간 복잡도는 O(n)으로 향상이 됩니다.

참고로 위 코드는 파이썬의 내장된 자료구조인 defaultdict를 사용해서 다음과 같이 간소화할 수 있습니다.

from collections import defaultdict

def solution(participant, completion):
    counter = defaultdict(int)
    for comp in completion:
        counter[comp] += 1
    for part in participant:
        if part in counter and counter[part] > 0:
            counter[part] -= 1
        else:
            return part

풀이 4

위 두 개의 풀이를 보면 각 참가자의 수를 세고 완주자의 수를 세어서 뺄셈을 하고 있는데요. 왜냐하면 각 선수의 이름이 문자열이어서 문자열 간에 바로 뺄셈을 하는 것이 불가능하기 때문입니다. 하지만 이 문자열을 숫자로 변환할 수 있다면 어떨까요?

선수의 이름을 상대로 hash() 함수를 사용하면 숫자를 얻을 수 있어서, 자연스럽게 선수 간에 사칙연산이 가능하게 되죠. 그럼 이 문제는 훨씬 간단하게 풀 수 있게 됩니다. 단순히 참가자를 모두 더한 후에 완주를 모두 빼면 완주하지 못한 딱 한 선수만 남을 것입니다. 그런데 그 선수의 값이 숫자로 되어 있기 때문에 변환 전에 문자열을 기억해놔야 합니다. 이를 위해서는 해시 테이블이 하나가 필요하겠습니다.

def solution(participant, completion):
    players = {}
    total = 0
    for part in participant:
        total += hash(part)
        players[hash(part)] = part
    for comp in completion:
        total -= hash(comp)
    return players[total]

이 풀이는 해시 테이블에 모든 참가자의 원래 이름 저장해야하므로 공간 복잡도가 O(n)이 됩니다. 시간 복잡도는 루프를 순차적으로 두 번 돌고 있으므로 O(n)이 됩니다.

풀이 5

선수 이름을 어떻게 숫자로 변환하는지를 배웠으니 이 문제는 XOR 연산자를 이용해서도 풀 수 있을 것 같습니다. 바로 같은 두 숫자를 XOR하면 0이 나오고, 0과 어떤 숫자를 XOR하면 그 숫자가 그대로 나온다는 성질을 이용하는 것인데요.

선수의 이름이 문자열이므로 hash() 함수를 사용하여 숫자로 변환해주면 XOR 연산자를 사용할 수 있습니다. 마찬가지로 숫자로 변환하기 전의 문자열을 기억하기 위해서 해시 테이블도 하나 필요합니다.

def solution(participant, completion):
    players = {}
    xor = 0
    for part in participant:
        xor ^= hash(part)
        players[hash(part)] = part
    for comp in completion:
        xor ^= hash(comp)
    return players[xor]

이 풀의 시간 복잡도와 공간 복잡도는 모두 O(n)으로 이전 풀이와 차이가 없습니다.

마치면서

정말로 다양한 방법으로 풀 수 있는 코딩 문제였습니다.

저는 개인적으로 면접관으로 코딩 인터뷰에 들어갈 때 이렇게 여러가지 방법으로 접근할 수 있는 문제를 선호합니다. 아무래도 정답이 한 가지인 문제보다는 지원자를 여러가지 길로 안내할 수 있으며 자연스럽게 다양한 주제에 대해서 대화를 나눌 수 있기 때문입니다.