[프로그래머스/JavaScript] 달리기 경주 (Feat. 찾기 연산의 시간복잡도)

 

☝🏻 1차 시도

function solution(players, callings) {
    let answer = [...players];
    
    for(let i = 0; i < callings.length; i++) {
        const calling = callings[i];
        const index = answer.indexOf(calling);
        const temp = answer[index - 1];
        answer[index - 1] = answer[index];
        answer[index] = temp;
    }
    
    return answer;
}

어질해지는 실행 시간에... 중단 했습니다... (ㅠㅠ)

 

🥚 중간 과정

function solution(players, callings) {
    let answer = [...players];
    
    for(let calling of callings) {
        // 호출된 선수의 순위(인덱스)를 찾는 시간 단축하는 방법이 필요해
        const index = answer.indexOf(calling);
        
        // 바꾸는 것은 시간이 오래 걸리지 않을 듯
        const temp = answer[index - 1];
        answer[index - 1] = answer[index];
        answer[index] = temp;
    }
    
    return answer;
}

 

이진 탐색을 사용해봐야 할지, 어떤 것이 가장 나은 방법일지 고민하던 중

(1) 배열을 중간 값을 기준으로 front 배열,  back 배열로 나누고

(2) 2개의 앞뒤 배열 중 has 메서드를 통해 calling(불린 선수)가 어디 있는지 확인하며

(3) 범위를 줄여나가 인덱스를 찾아볼까?

 

라고 고민했지만... 명확한 답변은 아닌 것 같아, 내일 다시 들여다 보기로 결정했습니다. (ㅠㅠ)

 

🧐 해결 과정

인덱스를 찾는 시간을 단축하는 방법을 고민하던 중... 시간복잡도를 먼저 확인해 보기로 했습니다.

indexOf를 통해 각 호출마다 선수의 순서를 찾을 때의 시간복잡도는 O(N)
i번 호출이 수행되므로 총 시간복잡도는 O(i*N)가 됩니다.

초기에 선수의 순위를 객체에 기록할 때에 O(N)의 시간이 소요되며,
각 호출에서 객체를 통해 선수의 순위를 가져오고 업데이트하는 데 O(1)의 시간이 소요됩니다.
따라서 i번의 호출 시 총 시간복잡도는 무려 ... O(i + N)

 

Object를 통해 인덱스에 접근할 때의 시간복잡도가 O(1) 상수 시간이 소요된다니...

이 문제를 통해 처음 알게된 아주 좋은 사실인 것 같습니다.

 

🍳 최종 결과

function solution(players, callings) {
    let answer = [...players];
    
    // (이름 : 순위) - (키 : 값) 객체를 초기화
    let playersObj = {};
    
    // 초기 선수의 순위를 playersObj에 기록
    for(let i = 0; i < answer.length; i++) {
        playersObj[answer[i]] = i;
    }
    
    for(let calling of callings) {
        // Object로 호출된 선수의 순위(인덱스)를 찾는 시간 단축
        const index = playersObj[calling];
        
        const temp = answer[index - 1];
        answer[index - 1] = answer[index];
        answer[index] = temp;
        
        // 호출된 선수와 그 앞의 선수의 순위를 업데이트
        playersObj[calling] = index - 1;
        playersObj[temp] = index;
    }
    
    return answer;
}

 

📝 정리

찾기 연산에서의 시간복잡도를 정리하며 이번 글 마무리하겠습니다 👋🏻

배열에서의 찾기 (indexOf 사용)
배열에서 indexOf 메서드를 사용하여 원소를 찾을 때, 배열의 처음부터 끝까지 순회하며 일치하는 원소를 찾습니다.
이 연산은 순차적으로 이루어지기 때문에 원소가 배열의 맨 앞에 있는 경우 시간복잡도는 O(N)이 됩니다.

객체에서의 찾기
객체에서는 키를 사용하여 바로 찾을 수 있습니다. 키-값 쌍은 해시 맵과 유사하게 구현되어 있어,
특정 키에 대한 값에 바로 접근할 수 있습니다. 따라서 시간 복잡도는 O(1)이 됩니다.