[알고리즘 || 프로그래머스] 달리기 경주

function solution(players, callings) {
    //player 의 배열 -> callings 의 순서 에 해당한는 선수와 그 앞의 선수의 번호를 바꿈
    //callings 를 foreach 로 돈다
    //callings 에 이름을 players 에서 indexOf 로 찾고, 
    //index-1 과 순서를 바꾼다. => 이전 선수를 찾고, 먼저 이름을 넣는다.
    
    callings.forEach(call => {
        const callIndex = players.findIndex(v => v === call)
        const fall = players[callIndex - 1];
        players[callIndex] = fall;
        players[callIndex - 1] = call;
        console.log(players)
    });
    return players
}

 

첨에 아주 간단하게 순서를 먼저 쓰고 이렇게 작성했는데, 

예상대로 시간초과가 떴다.

 

for 문 안에서 findIndex 를 했기 때문에 n^2 가 된 듯,,, 하다!

 

그렇다면 index 를 계속 찾는 것 대신 다르게 기록하는 방법을 찾아야했다.

map 을 이용해 풀어봤다.

function solution(players, callings) {
    const order = new Map();
    players.forEach((name, index) => {
        order.set(name, index);
    })
    callings.forEach(call => {
        const callIndex = order.get(call)
        const fall = players[callIndex - 1];
        players[callIndex] = fall;
        players[callIndex - 1] = call;
        order.set(call, order.get(call) - 1);
        order.set(fall, order.get(call) + 1);
    });
    return players
}

Map(5) { 'mumu' => 0, 'soe' => 3, 'poe' => 4, 'kai' => 1, 'mine' => 2 } 
[ 'mumu', 'kai', 'mine', 'soe', 'poe' ]

 

그냥 객체를 사용할 수도 있었는데, 

map 을 사용한 근거가 사실 없었다... 

그래서 찾아봄. 

아래 링크에 그 차이가 잘 설명되어 있다. 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map#%EA%B0%9D%EC%B2%B4_vs_%EB%A7%B5

Map - JavaScript | MDN

 

 

Map 객체는 키-값 쌍인 집합입니다. 한 Map 에서의 키는 오직 단 하나만 존재 합니다.
이는 Map 집합의 유일성입니다. 

 

이쯤 되니 얼마나 차이나나 궁금해짐. 

 

function solution(players, callings) {
    const order = {};
    players.forEach((name, index) => {
        order[name] = index;
    })
    callings.forEach(call => {
        const callIndex = order[call];
        const fall = players[callIndex - 1];
        players[callIndex] = fall;
        players[callIndex - 1] = call;
        order[call] = callIndex - 1;
        order[fall] = callIndex;
    });
    return players
}

 

 

Map 을 이용한 결과 vs Object 를 이용한 결과

 

오 map 을 사용한 결과가 대체로 더 적어보인다.

그리고 배열의 수가 제일 많은 11, 12, 13 케이스에선 map 이 무조건 빠르다고 할 순 없지만 

11번 처럼 시간복잡도가 확 올라가는 경우는 없다. 

 

시간 복잡도가 클 것으로 예상될 때 map 을 잘 사용해주면 성능 개선에 유의미한 결과가 있을 것 같다.