프로그래머스_달리기 경주

출처 : 프로그래머

■ 해결 방법

callings에 있는 값을 players에 순회해서 찾으려면 50,000 * 1,000,000의 시간복잡도가 소요된다. 

따라서 O(n) 이하의 시간 복잡도로 풀 수 있는 방법을 찾아야 한다. 

나는 players의 있는 값들을 순위를 매겨주었다. 

{ mumu : 1, soe : 2, poe : 3, kai : 4, mine : 5} 이런식으로 해준 다음 callings에 불린 값과 그 앞의 값의 순서를 바꿔주는 형태로 진행했다. 이 때 주의해야 할 것은 players의 순서만 바꾸어 주는 것이 아닌, 순위도 값이 변경해주어야 하는 것이다. 

 

■ 코드 

function solution(players, callings) {
    var answer = [];
    let playersDict  = []
    let orderNum = 0;
    for(let i = 0; i < players.length; i++){
        playersDict[players[i]] = orderNum++; 
    }
    for(let i = 0; i <  callings.length; i++){
        let tmpA = playersDict[callings[i]];
        let tmp = players[playersDict[callings[i]]];
        players[playersDict[callings[i]]] = players[playersDict[callings[i]] - 1];
        players[playersDict[callings[i]] - 1] = tmp;
        playersDict[ players[playersDict[callings[i]]]] = tmpA;
        playersDict[callings[i]] = tmpA - 1;
    }
    return players;
}