[프로그래머스/Javascript] Lv.1 달리기 경주

프로그래머스

 

 

✓ 풀이과정

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

  for (const player of callings) {
    let index = answer.indexOf(player);
    [answer[index - 1], answer[index]] = [answer[index], answer[index - 1]];
  }

  return answer;
}

 

첫 시도는 불린 선수들의 위치를 찾아서 상위 랭크 선수와 위치만 교체하면 되겠다고 생각했는데

index를 찾기 위해 사용한 indexOf 가 for문 안에 포함되며 시간복잡도가 증가해 시간초과가 발생했습니다

→ indexOf 대체 필요

 

 

 

✓ 최종코드

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

  for (let i = 0; i < answer.length; i++) {
    const x = answer[i];
    rank.set(x, i);
  }

  for (const x of callings) {
    let nextRank = rank.get(x);
    let prevRank = nextRank - 1;

    rank.set(answer[prevRank], nextRank);
    rank.set(answer[nextRank], prevRank);

    [answer[prevRank], answer[nextRank]] = [answer[nextRank], answer[prevRank]];
  }

  return answer;
}

 

별도로 불린 선수의 index를 얻을 수 있는 방법을 찾아보다가 js의 Map을 사용하는 방법으로 시도했습니다

선수별로 등수를 저장할 rank map을 선언하고 이후 호명될 때마다 해당 선수의 등수와 추월할 선수의 등수로 player를 찾아서 위치를 변경하는 방식으로 구현했습니다