[Algorithm] 달리기 경주 - JavaScript

프로그래머스 - 달리기 경주
난이도 : Level 1
정답률 : 39%

▶ 풀이

Player 를 index 를 value로 가진 Map 데이터로 전환 후
callings 배열을 순회하며 경주 순위를 재설정

function solution(players, callings) {
    const playerMap = new Map();
    // 멥 데이터로 전환
    players.forEach((x, idx) => {
        playerMap.set(x, idx);
    })
    callings.forEach((v, idx) => {
       // 멥 세팅
        playerMap.set(v, playerMap.get(v) - 1);
        playerMap.set(players[playerMap.get(v)], playerMap.get(v) + 1);
      // player 배열 세팅
        const tmp = players[playerMap.get(v) + 1];
        players[playerMap.get(v) + 1] = players[playerMap.get(v)];
        players[playerMap.get(v)] = tmp;
    });
    return players;
}

▶ 삽질

function solution(players, callings) {
    callings.forEach(v => {
        const findPlayer = players.findIndex(p => p === v);
        const tmp = players[findPlayer];
        players[findPlayer] = players[findPlayer - 1];
        players[findPlayer - 1] = tmp;
    });
    return players;
}

-> findIndex 로 인덱스를 찾을 경우 시간복잡도가 O(n^2) 이 된다.

▶ 다른 풀이

function solution(players, callings) {
    const rank = {};
    players.forEach((c,i) => rank[c] = i);
    for(const winner of callings){
        let winnerI = rank[winner];
        let loserI = winnerI - 1;

        rank[winner]--;
        rank[players[loserI]]++;

        players[winnerI] = players[loserI];
        players[loserI] = winner;
    }
    return players;
}
같은 방식이지만 가독성 면에서 훨씬 보기 좋다고 생각되는 풀이

굳이 Map 을 고집할 필요는 없었을 것 같다.

▶ 고찰

맵 안에서 findIndex를 하는 방법을 떠올리는 것에는 오랜 시간이 들지 않았는데, 그 방법이 타임이 걸려 Map 을 하는 방식을 떠올리는데 시간이 오래 걸렸다.
맵을 두 개 만들지 않고, 배열의 인덱스로 바꾸는 방법은 괜찮게 떠올린 것 같다.