프로그래머스. 코딩테스트 고득점 Kit.
해시. 1단계

효율성 테스트 통과 실패

function solution(participant, completion) {
    for(let i = 0; i < completion.length; i++){
        let comp = completion[i];
        
        if(participant.includes(comp)){
            let index = participant.indexOf(comp);
            
            participant.splice(index, 1);
        }
    }
    
    let answer = participant[0];
    
    return answer;
}

indexOf와 splice 모두 시간 복잡도가 O(n)으로
입력 데이터의 수가 커지면 그만큼 시간이 오래 걸린다.
이를 해결해야한다.

효율성 테스트 1/5 통과

function solution(participant, completion) {
    // sort를 통해 사전순으로 참가자 정렬
    participant.sort();
    completion.sort();
    
    let count = 0;
    
    while(participant.length > 0){
        let pLength = participant.length;
        
        // 가장 앞부터 비교를 진행한다
        // 만약, 두 배열의 값이 다르면 그 때의 participant가 아직 들어오지 않은 것이다.
        if(participant[count] === completion[count]){
            participant.shift();
            completion.shift();
        }
        
        // participant의 길이가 변하면 인덱스를 다시 0으로 초기화
        // 변하지 않았다면, 위 if문을 만족하지 못한 것이므로 while문 break
        if(pLength !== participant.length){
            count = 0;
        } else {
            break;
        }
    }
    
    let answer = participant[0];
    
    return answer;
}

이번에는 sort로 두 배열을 정렬해서 가장 앞 부분만 비교를 하고자 한다.
sort는 시간 복잡도가 O(nlog(n))이다.

가장 앞만 비교하고 다른 순간 반복이 종료된다.
최대한 배열 내부를 왔다갔다하는 탐색을 줄이고자 했다.
시간은 압도적으로 줄어들었지만 효율성 테스트를 1/5개밖에 통과하지 못했다.

효율성 테스트 4/5 통과

function solution(participant, completion) {
    // sort를 통해 사전순으로 참가자 정렬
    participant.sort();
    completion.sort();
    
    let answer = "";
    
    let count = 0;
    
    while(participant.length > 0){
        // 가장 앞부터 비교를 진행한다
        // 만약, 두 배열의 값이 다르면 그 때의 participant가 아직 들어오지 않은 것이다.
        if(participant[count] !== completion[count]){
            answer = participant[count];
            
            break;
        }
        
        count++;
    }
    
    return answer;
}

이번에는 if 조건을 정반대로 바꿨다.
연산을 조금이라도 더 줄이기 위해서였다.
단 1개의 효율성 테스트를 통과하지 못했다...

solution

function solution(participant, completion) {
    // sort를 통해 사전순으로 참가자 정렬
    participant.sort();
    completion.sort();
    
    let count = 0;
    
    while(true){
        // 가장 앞부터 비교를 진행한다
        // 만약, 두 배열의 값이 다르면 그 때의 participant가 아직 들어오지 않은 것이다.
        if(participant[count] !== completion[count]){
            return participant[count];
        }
        
        count++;
    }
}

이젠 answer에 넣는 것 조차도 없애버렸다. break도 없다.
두 배열의 차이가 발생하면 바로 return을 진행한다.
모든 효율성 테스트를 통과했다.

참고 자료

참고 자료 1