23.04.15. programmers 코딩테스트 문제 풀기[1]

또 몇가지 풀다가 막혔지만 풀긴 푼 문제.

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

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

쉽다고 생각했다. 실제로 구현 자체는 쉬웠으나, 효율성에서 실패해서 당황했다. 물론 효율적이라 생각은 안했지만...

 

우선 생각나는대로 아래처럼 구현했다.

function solution(participant, completion) {
    for (i of completion) {
        participant.splice(participant.indexOf(i), 1)
    }
    return participant[0];
}

indexOf로 completion의 요소를 participant에서 찾고, splice로 잘라내면, 결국 한개의 요소가 남은 participant의 0번째 요소를 반환하면 될 것이라고 생각했다.

 

문제는 효율성에서 시간초과가 된 것. 그래서, array를 검색하고, 조작하는 것이 시간이 오래걸릴 것으로 판단하고 sorting해서 비교하는 방법을 생각했다. 다행히 효율성에서 통과.

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

그래도 썩 마음에 드는 방식은 아니다.

 

다른 사람이 푼 아래 코드를 살펴보니, 객체화 해서 비교하는 방식을 사용했더라. 속도도 조금 더 빨랐다. 

function solution(participant, completion) {
    const completeObj = {} // 완주자 명단 만들기 
    completion.forEach(name => { // 명단에 없는 이름이면 { 이름: 1 } 
        if (!completeObj[name]) completeObj[name] = 1 // 이미 올라간 이름이면 등장횟수++ 
        else completeObj[name]++
    }) // 참가자와 완주자 명단 비교 
    return participant.find(name => { // 현 참가자가 완주자 명단에 있고, 값이 0이 아니면 값-- 
        if (completeObj[name]) completeObj[name]-- // 명단에 없거나 값이 0이면 리턴 
        else return name
    })
}

이유를 유추해보면, 내 첫번째 실패 코드는 completion의 요소 수만큼 participant 요소 전체를 검색하는 걸 반복한다.

즉, O(N^2)이 되는데, 거기에 splice까지 하니.. splice의 동작 방법을 모르지만 최소 O(N^2)에서 최대 O(N^3)이 될 듯.

 

두번째 성공했지만 마음에 들지 않는 코드는 participant 정렬과 completion정렬에서, O(NlogN)으로 (아마도) 처리되었고, 비교 코드는 O(N)이니, 적당히 O(NlogN)에서 정리된 것 같다.

 

마지막 다른 사람의 풀이 코드는, completion과 participant를 한번씩만 순회하면서 끝나기때문에 O(N)으로 끝나는 것으로 보인다.