프로그래머스 < 달리기 경주 > JavaScript

📍문제 링크

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

 

📍알고리즘 분류

- 구현

 

📍문제 풀이

- 달리기 경주중인 상황에서, 현재 선수들의 이름이 순위 순서로 배열로 주어진다 -> string[]

- 어떤 선수가 1번 추월에 성공하면, 그 선수의 이름을 추월한 순으로 배열로 저장한다 -> string[]

추월 기록 배열을 순회하며 현재 순위별 선수 이름 배열을 업데이트하고 출력하라

 

단순하게 swap 함수를 만들어서 배열을 직접 조절했는데, 시간 초과가 발생했다.

시간 복잡도가 O(N^2)가 되는데다, 배열에서 원소를 움직이는 작업은 계산 비용이 크기 때문인 듯 하다

 

어떻게 할까.. 고민하다가 하나의 객체만 활용해서 시간을 줄이려고 해봤는데,

추월한 선수 이름을 받을 때, 앞 선수를 확인하려면 어차피 O(N^2)가 소요되어 버린다.

 

그래서 다른 방법을 고민하다가 2개의 객체를 활용해서 탐색의 시간 복잡도를 O(1)로 줄일 수 있었다

 

📍코드 (JavaScript)

const players = ["mumu", "soe", "poe", "kai", "mine"];
const callings = ["kai", "kai", "mine", "mine"];

function solution(players, callings) {
  const rankKeyObj = {};
  const nameKeyObj = {};
  players.forEach((player, idx) => {
    rankKeyObj[idx] = player;
    nameKeyObj[player] = idx;
  });
  function swap(name) {
    const currentIdx = nameKeyObj[name]; // 현재 순위
    const formerPlayer = rankKeyObj[currentIdx - 1]; // 앞 플레이어
    nameKeyObj[formerPlayer] = currentIdx; // 순위 하락
    nameKeyObj[name] = currentIdx - 1; // 순위 상승
    rankKeyObj[currentIdx - 1] = name; // 순위 상승
    rankKeyObj[currentIdx] = formerPlayer; // 순위 하락
  }
  callings.forEach((name) => swap(name));
  return Object.values(rankKeyObj);
}

console.log(solution(players, callings));