Programmers Algorithm - 달리기 경주

다음은 Programmers 의 Lv1 달리기 경주 문제에 대한 해결 과정이다.
players 가 주어지고 callings 가 1 <= callings <= 1000,000 의 크기로 주어지게 된다.

중요한 점은 callings 를 루프 돌면서 swap 하는 것이라는 생각이 들었고 이에 다음의 코드를 작성해서 제출했다.

const swap = ( players, callPlayer) => {
	const callPlayerIndex = players.findIndex(player => player === callPlayer);
	if(callPlayerIndex === -1) {
		return new Error('None Player');
	}
    
	const swapedPlayer = players[callPlayerIndex - 1];
	players[callPlayerIndex] = swapedPlayer;
	players[callPlayerIndex - 1] = callPlayer;
}
function solution(players, callings) {
    const tempPlayers = [...players];    
    callings.forEach(calling => {
        swap(tempPlayers, calling);
    });
    return tempPlayers;
}

해당 풀이는 시간 초과로 실패했는데 가장 큰 이유는 forEach method 내부에서 findIndex 를 하고 있기 때문에 시간 복잡도가 O(n^2) 이 나오기 때문이다.

playrs 의 각각의 순위는 callings 의 순서에 영향을 받기 때문에 callings 루프를 돌지 않을 수는 없다. 그럼 findIndex 를 swap 로직에서 제거를 해야 하고 이를 위해 플에이어에 대한 순위를 매번 찾는게 아니라 미리 알고 들고 있기 위해 Map 을 활용했다.

const swap = (players, callPlayerIndex) => {
        const swapedPlayer = players[callPlayerIndex - 1];
        const callPlayer = players[callPlayerIndex];
        players[callPlayerIndex] = swapedPlayer;
        players[callPlayerIndex - 1] = callPlayer;
}
function solution(players, callings) {
    const tempPlayers = [...players];    
    const playerMap = new Map(tempPlayers.map((tempPlayer, index) => [tempPlayer, index]));
    callings.forEach(calling => {
        const callPlayerIndex = playerMap.get(calling);
        swap(tempPlayers, callPlayerIndex);
        playerMap.set(calling, callPlayerIndex - 1);
        playerMap.set(tempPlayers[callPlayerIndex], callPlayerIndex);
        
    });
    return tempPlayers;
}

Map 을 만드는데 걸린 시간은 평균적으로 O(n) 이고, Callings 루프를 도는 로직은 O(k) 라고 할 때, 그 외 각각의 연산은 O(1) 의 시간이 걸리기 때문에 최종적으로 O(n + k) 의 시간이 걸리게 된다.

통과.

다른 사람들의 풀이를 봤을 때, 다른 사람들도 비슷하게 풀었다.