알고리즘(Python, JavaScript) - 완주하지 못한 선수

Input

1
2
participant = ["John", "David", "Becky"]
finisher = ["Becky", "David"]

Expected Output

1
result = "John"

목표

참가자 리스트와 완주자 리스트가 주어지고 그 두 리스트를 비교하여 어떤 선수가 완주하지 못하였는지 구하는 것

조건

  • 선수의 수는 1명 이상 100,000명 이하.
  • finisher의 길이는 participants의 길이보다 1 작다.
  • 선수 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어짐.
  • 선수 중에는 동명이인이 있을 수 있음.

코드

Python

1
2
3
4
5
6
7
def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p,c in zip(participant, completion):
        if i != j:
            return i
    return participant[-1]

JavaScript

1
2
3
4
5
6
7
8
9
function solution(participant, completion) {
    participant.sort();
    completion.sort();
    for(let i in participant) {
        if (participant[i] !== completion[i]) {
            return participant[i];
        }
    }
}

해설

  • 두 리스트를 set으로 변경하고 차이를 구한 뒤 다시 리스트로 변경하는 것은 동명이인이 있는 경우를 통과 할 수 없음
  • 두 리스트를 정렬하고 함께 재귀하는 동안 다른 이름이 재귀하게되면 participant의 이름이 완주하지 못한 선수이다.
  • 만약 정렬에서 완주하지 못한 선수가 가장 끝으로 정렬된 경우 그 선수까지 재귀하기전에 재귀가 끝나므로 그 후에는 participant의 마지막 선수를 return하면 된다.