프로그래머스의 완주하지 못한 선수 문제를 함께 풀어보도록 하겠습니다.
문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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)으로 이전 풀이와 차이가 없습니다.
마치면서
정말로 다양한 방법으로 풀 수 있는 코딩 문제였습니다.
저는 개인적으로 면접관으로 코딩 인터뷰에 들어갈 때 이렇게 여러가지 방법으로 접근할 수 있는 문제를 선호합니다. 아무래도 정답이 한 가지인 문제보다는 지원자를 여러가지 길로 안내할 수 있으며 자연스럽게 다양한 주제에 대해서 대화를 나눌 수 있기 때문입니다.