[프로그래머스] 달리기 경주

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

프로그래머스

---

1차 제출

function solution(players, callings) {
    for (let calling of callings) {
        let index = players.indexOf(calling);
        if (index > 0) {
            [players[index - 1], players[index]] = [players[index], players[index - 1]];
        }
    }
    return players;
}

결과 : 75점

문제점 : indexOf는 배열에서 요소를 찾기 위해 선형 탐색을 수행하기 때문에, 배열 크기가 커질수록 속도가 느려질 수 있다.

 

2차제출

function solution(players, callings) {

 	# player명, index로 map 생성
    let playerIndices = new Map(players.map((player, index) => [player, index]));

    for (let calling of callings) {
    	# calling 에 해당하는 index 조회
        let index = playerIndices.get(calling);
        if (index > 0) {
            let prevPlayer = players[index - 1];
            players[index - 1] = players[index];
            players[index] = prevPlayer;

            playerIndices.set(calling, index - 1);
            playerIndices.set(prevPlayer, index);
        }
    }
    return players;
}

결과 : 100점

---

문제가 쉽다고 생각하고 단순하게 풀었는데 성능이슈로 불합격이 떠서 놀랐다.

확인해보니 indexof는 선형 탐색을 수행하기 때문에, 배열 크기가 커질수록 속도가 느려질 수 있다고한다.

매 반복마다 indexof로 index를 찾는 방법말고, 처음부터 players의 요소와 인덱스를 매핑한 map객체를 만들어서 조회한 뒤 업데이트 하는 방식으로 진행하였다.