완주하지 못한 선수

코딩 테스트 문제

프로그래머스

[시간복잡도 비교표]

문제 접근)
마라톤 경기의 참여한 선수가 100,000명 이하이므로 시간복잡도 10^5이므로 10^8을 넘으면 안되므로 시간복잡도 O(N^2) 미만의 알고리즘으로 해결하면 됩니다. 즉, O(n log n), O(n), O(log n), O(1) 방식으로 해결하면 됩니다.

Completion의 길이는 participant의 길이보다 1 작다라는 말은 한명만 완주하지 못한 선수가 나온다는 의미이므로 두개의 배열을 비교하는 로직으로 해결하면 됩니다.

동명이인이 있을 수 있다라는 말은 해시맵을 이용한 방법으로 해결하기 어려울 수 있습니다. 해시맵은 동일한 값은 제거하기 때문에 동명이인이 여러명인 경우 구분이 안가기 때문입니다.

 

풀이

function solution(participant, completion) {
    const sortedParticipant = participant.sort();
    const sortedCompletion = completion.sort();
    
    for (const i in sortedParticipant) {
        if (sortedParticipant[i] !== sortedCompletion[i]) {
            return sortedParticipant[i]
        }
    }
}

 

문제접근 방법을 바탕으로 해결해보도록 하겠습니다.

처음에 시간복잡도 O(n log n)방식으로도 해결 할 수 있으므로, sort는 시간복잡도 O(n log n) 방식을 갖습니다. sortedParticipant 와 sortedCompletion의 시간복잡도는 O(n log n) + O(m log m) 두개를 더해도 O(n log n) 방식으로 출력되며, for문은 시간복잡도 O(n) 방식이므로 O(n log n) + O(n)은 O(n log n) 방식으로 출력됩니다.

 

알파벳은 소문자로 이루어져있다는 sort 정렬할 때 대소문자의 대한 sort를 고려하지 않아도 된다는 의미이므로 completion과 perticipant를 sort 정렬해서 동일한 알파벳 순서대로 정렬되게 배열을 정렬합니다.

completion의 길이는 participant의 길이보다 1 작으므로 두개의 배열을 비교해서 다른 값이 출력되는 부분이 완주하지 못한 선수의 이름이 되는 것입니다.

 

(참고)
입출력 예)
Case 1

{ sortedParticipant: [ 'eden', 'kiki', 'leo' ], sortedCompletion: [ 'eden', 'kiki' ] }

Case 2

{ sortedParticipant: [ 'filipa', 'josipa', 'marina', 'nikola', 'vinko' ], sortedCompletion: [ 'filipa', 'josipa', 'marina', 'nikola' ] }

Case 3

{ sortedParticipant: [ 'ana', 'mislav', 'mislav', 'stanko' ], sortedCompletion: [ 'ana', 'mislav', 'stanko' ] }