프로그래머스) 달리기경주 javascript

프로그래머스의 Level1 짜리 문제임에도 불구하고 정답률이 낮은 문제입니다.

문제만 읽고 나면 정말 간단해 보이는 문제 같은데, 정작 중요한 시간초과가 나옵니다.

시간초과를 낸 문제 해결 방법을 먼저 보겠습니다.

 

문제 해결 방식) 

위의 callings를 한번씩 읽으면서 players의 해당 선수의 위치와, 그 앞선수의 자리를 바꿔주기만 하면 되는 것이다.

function solution(players, callings) {
    let answer = players.slice();
    callings.map((p,i) => {
        let pos = answer.indexOf(p);
        swapWithPrevious(answer, pos);
    })
    return answer;
}

function swapWithPrevious(array, index) {
  if (index === 0 || array.length <= 1) {
    return;
  }

  let temp = array[index];
  array[index] = array[index - 1];
  array[index - 1] = temp;
}

swapWithPrevios라는 배열의 특정 index 값과 index-1의 위치를 바꿔주는 함수를 만들고, 

callings 를 순회하면서 players의 해당 선수의 위치 값을 찾고 바꿔주는 방법입니다.

 

여기서 시간을 낭비하는 곳이 크게 2가지가 나온다.

 

① indexOf 사용

callings는 최대 100만개의 요소를 갖는다.

그 요소들을 모두 돌면서 playsers에서 indexOf를 하는 건 제일 큰 시간 낭비였다.

indexOf는 모든 요소를 순회하면서 찾기 때문에 선형 시간복잡도를 갖는다.

 

②  swapWithPrevios 호출을 함수 밖에 선언

swapWithPrevios 함수를 함수 밖에 선언하며, callings의 요소 수만큼 호출하게 되는 낭비가 발생한다.

 

 

위 두가지를 수정한 코드입니다.

function solution(players, callings) {
  let answer = [...players];
  let indexMap = new Map();

  answer.forEach((player, index) => {
    indexMap.set(player, index);
  });

  callings.forEach((player) => {
    let pos = indexMap.get(player);
    if (pos > 0) {
      let temp = answer[pos];
      answer[pos] = answer[pos - 1];
      answer[pos - 1] = temp;
      indexMap.set(answer[pos], pos);
      indexMap.set(answer[pos - 1], pos - 1);
    }
  });

  return answer;
}