[JS] 달리기 경주

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

프로그래머스

문제 이해

calling에 불린 사람은 한 등수 앞으로 나가갔다는 것을 의미함. 현재 등수와 앞사람과 위치를 어떻게 바꿀지 생각해봐야 함.

 

방법1

맨처음에는 callings에 있는 사람의 현재 등수를 찾아 players에서 제거하고 한 등수 앞에 추가하려고 했다.

function solution(players, callings) {

  for (const calling of callings) {
    const curIdx = players.indexOf(calling);
    players.splice(curIdx, 1);
    players.splice(curIdx - 1, 0, calling);
  }

  return players;
}

하지만 정답은 잘 나오는 것 같으나 시간 초과가 발생했다. 그래서 모든 calling에 대해 수행해서 오래 걸리는 것 같아서 불린 횟수를 정리해서 수행하려고 했다. 그랬더니 정답도 잘 안나와서 다른 방법을 찾아보기로 했다.

 

방법2

찾아보니 배열의 indexOf 메소드가 시간복잡도 O(n)으로 오래 걸린다는 말이 있었다. 앞에서부터 차례로 해당 값이 나올 때까지 찾아본다는 것이다. 그래서 dict에 각 player의 현재 순위와 현 순위에 누가 있는지 저장했다. 이후 call 되는대로 dict를 업데이트 해주었다.

function solution(players, callings) {
  var answer = [];

  const ranking = {};
  players.forEach((player, idx) => {
    ranking[player] = idx;
    ranking[idx] = player;
  });

  for (const calling of callings) {
    // call된 사람의 등수
    const curRank = ranking[calling];
    // call된 사람의 앞 사람
    const front = ranking[curRank - 1];

    // 앞 사람 등수 +1
    ranking[front]++;
    // call된 사람 등수 -1
    ranking[calling]--;
    // ranking update
    ranking[curRank - 1] = calling;
    ranking[curRank] = front;
  }
  
  for(let i = 0, n = players.length; i < n; i++) {
    answer.push(ranking[i])
  }

  return answer;
}

위와 같은 방법으로 `indexOf` 메소드가 가진 시간 복잡도 문제를 해결할 수 있었다.