프로그래머스 L1 - 달리기 경주

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

프로그래머스

 

function solution(players, callings) {
    for(const name of callings){
        let idx =players.indexOf(name);
        [players[idx-1],players[idx]] = [players[idx],players[idx-1]];
    }
    return players;
}

이렇게 작성하면 시간 초과가 나온다.

왜냐하면 players의 최댓값은 5만이고, callings의 최댓값은 100만이다.

따라서 indexOf를 사용하게 되면 5만 * 100만이 되므로 시간초과가 날 수 밖에 없다.

따라서 선수들의 등수를 참조하기 위해서는 indexOf 처럼 O(N)만큼의 시간복잡도가 걸리는 로직이 아니라

해시맵과 같이 O(1)의 시간복잡도가 걸리는 로직을 생각해야한다.

자료구조를 배열, 해시맵 두 개를 활용해서 배열에는 등수에 대한 이름을 저장하고, 해시맵에는 이름에 대한 등수를 저장한다.

 

function solution(players, callings) {
    const map = new Map();
    for(let i = 0; i < players.length ; i++){
        map.set(players[i],i);
    }
    for(const name of callings){
        [players[map.get(name)], players[map.get(name)-1]] = [players[map.get(name)-1], players[map.get(name)]]; 
        map.set(players[map.get(name)], map.get(players[map.get(name)])+1);
        map.set(name,map.get(name)-1);
    }
    return players;
}

 

[players[map.get(name)], players[map.get(name)-1]] = [players[map.get(name)-1], players[map.get(name)]];

이 코드는 해시맵에 저장된 등수를 참조해서 배열 요소의 위치를 바꾸는 코드이다.

 

map.set(players[map.get(name)], map.get(players[map.get(name)])+1);
map.set(name,map.get(name)-1);

등수가 바뀌었으니 해시맵의 value값도 변경해야한다.