[알고리즘] 코딩테스트 연습 - [JavaScript] 달리기 경주

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

1. 문제 풀이

 문제 설명 자체는 쉬운 문제입니다. 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어집니다.

 

 즉 우리는 배열 players의 원소들의 위치를 swap하여 관리하는 것이 전부라고 볼 수 있습니다(해설진이 부른 선수와 그 앞 선수의 위치를 바꾸는 연산이 전부!).

 

 

2. 실패 코드(시간 초과, 75점)

function solution(players, callings) {
    for (let call of callings) {
    	// 해설진이 부른 선수의 위치를 변수 idx의 저장
        let idx = players.indexOf(call);
        
		// idx번째에 있던 player가 추월하였으므로 idx-1번째 선수와 idx번째 선수의 위치 변경
        let tmp = players[idx - 1];
        players[idx - 1] = players[idx];
        players[idx] = tmp;
    }
    return players;
}

 

 추월한 선수와 추월 당한 선수를 swap하는 것이 문제의 핵심 연산이라고 생각하였기에 해설진이 부른 선수의 위치(idx)를 얻어내는 것이 가장 중요하다고 생각하였습니다.

 

 Array.prototype.indexOf()를 사용하여 해당 선수의 위치를 얻는 것에는 성공하였으나 indexOf() 자체의 시간 복잡도는 O(n)이기 때문에 시간 초과 문제가 발생하였습니다.

 

 이 문제에서 players의 최대 크기는 50,000이며 callings의 최대 크기는 1,000,000이기 때문에 O(n)의 시간 복잡도를 개선할 필요가 있었습니다.

 

 

3. 정답 코드

function solution(players, callings) {
    let playerMap = new Map();
    
    for (let i = 0; i < players.length; i++) {
        playerMap.set(players[i], i);
    }
    
    for (let call of callings) {
        // map을 idx를 찾는 용도로 사용
        let idx = playerMap.get(call);
        
        // swap
        let tmp = players[idx - 1];
        players[idx - 1] = call;
        players[idx] = tmp;
        
        // 바뀐 등수를 playerMap에도 반영
        playerMap.set(call, idx - 1);
        playerMap.set(tmp, idx);
    }
    return players;
}

 

 자바스크립트의 자료구조 Map을 사용하여 코드 개선을 진행하였습니다. Map은 키(key)와 값(value)쌍을 저장하는 자료 구조입니다. 각 키는 고유하며 키를 사용하여 값을 빠르게 검색할 수 있는 특징을 가지고 있습니다(.get(key)는 O(1)의 시간 복잡도를 갖습니다!).

 

 기존 코드에서 추가된 부분은 Map을 생성하고 초기화한 부분과 callings의 원소들을 순회할 때마다 바뀐 등수를 map에도 반영해주는 부분입니다.

 

이를 통하여 주요 연산이었던 idx를 찾는 연산을 O(n)에서 O(1)까지 효율성 개선을 할 수 있었으며 모든 테스트 케이스를 통과하였습니다.