마라톤에 참여한 선수들 그리고 마라톤은 완주한 선수들의 명단을 받는다. 그중 마라톤에는 참여했지만 완주하지 못한 선수들의 이름을 착출해야한다.

내가 생각한 방법으론 참여자 명단에는 있지만 완료자 명단에는 없는 값을 뽑아내면 된다. 참여자 명단의 이름을 하나씩 돌면서 그값이 완료자 명단에 없으면 이름을 반한하면 된다.

function solution(participant, completion) {
    var answer = '';

    // 참여자 명단에는 있고 완료자 명단에는 없는 값을 찾는다. 
    participant.forEach( ele => {
        if( !completion.includes(ele) ){
            answer = ele;            
        } 
        const idx = completion.indexOf(ele);
        if( idx > -1) completion.splice(idx, 1);
    })
    return answer;
}

정확성에서는 만점이 나왔지만, 효율성에서는 0점이 나온 코드다.

왜 그런지 코드를 분석해보자. 시간복잡도를 유추해보자. 먼저 참여자 명단을 도는데 걸리는 시간 복잡도 n, 참여자를 완료자 명단에있는지 찾는데 걸리는 시간 복잡도 n으로 n^2이다.

어떻게 더 효율성을 올릴수 있을지 고민해보자.

function solution(participant, completion) {
    let answer = '', i = 0;

    participant.sort(); 
    completion.sort();
    
    // 참여자 명단의 인원만큼 반복 
    while( i < participant.length ){
        // 참여자 명단과 완주자 명단이 다른 참여자는 완주하지 못한 경우
        if( participant[i] !== completion[i] ){
            return participant[i];
        }
        i++;
    }
    
    // 참여자 명단과 완주자 명단이 다같았다면, 참여자 명단의 마지막 값이 미완주
    answer = participant.pop();
    return answer;
}

정렬된 참여자 명단과 완주자 명단을 비교하여 다른경우 참여자가 완주하지 못한 경우임을 알 수 있다.

시간복잡도로 따지면 참여자 명단 정렬 n, 완주자 명단 n, 참여자 명단의 인원만큼 반복 n이므로 총 3n 시간복잡도는 n이다.

코드에 먼가 아쉬운점이 있다. let i, while문을 사용하는게 나쁜건 아니지만 명확한 의미 전달이 없어 아쉬웠다. 좀더 명확하게 표현해보자.

function solution(participant, completion) {
    let answer = '';

    participant.sort(); 
    completion.sort();
    
    // 참여자 명단의 인원만큼 반복 
    for( let i in participant){
        // 참여자 명단과 완주자 명단이 다른 참여자는 완주하지 못한 경우
        if( participant[i] !== completion[i] ){
            return participant[i];
        }
    }
}

참여자 명단을 반복하기위한 방복으로 for을 사용하였다. 더욱 명확하게 의미가 전달된다.ㅎㅎ