[Javascript] 프로그래머스 - 달리기 경주

문제 설명

얀에서는 매년 달리기 경주가 열립니다.

• 각 선수는 자기 앞의 선수를 추월할 때 해설진에 의해 이름이 불립니다.
• 불린 이름의 선수가 바로 앞의 선수를 추월하며, 두 선수의 순위가 서로 바뀝니다.

입력으로 1등부터 현재 등수 순서대로 담긴 선수 이름 배열 players와, 해설진이 부른 이름 배열 callings가 주어집니다. 모든 추월이 끝난 후 최종 선수 순위를 반환하세요.

제한사항

1. 선수 배열 (players):
   • 길이: 5 ≤ players.length ≤ 50,000
   • 각 원소는 고유하며 알파벳 소문자로만 구성.
   • 문자열 길이: 3 ≤ players[i].length ≤ 10.
2. 추월 기록 (callings):
   • 길이: 2 ≤ callings.length ≤ 1,000,000
   • 추월 대상은 항상 players 배열에 포함된 이름.
3. 조건:
   • 1등인 선수의 이름은 불리지 않습니다.

해결 방법

알고리즘: 시뮬레이션

1. 순위 매핑 생성:
   • 선수 이름과 현재 순위를 매핑하는 Map 객체를 생성하여 빠른 조회 가능.
2. 추월 처리:
   • callings 배열을 순회하면서 추월된 선수와 추월한 선수의 순위를 업데이트.
   • players 배열과 Map 동기화:
     • players 배열에서 두 선수의 위치를 교환.
     • Map에서 순위를 업데이트.
3. 결과 반환:
   • 모든 추월이 처리된 후의 players 배열 반환.

시간 복잡도

1. Map 생성: O(n), n은 players 배열의 길이 (최대 50,000).
2. 추월 처리: O(1) 연산을 m번 수행, m은 callings의 길이 (최대 1,000,000).
3. 전체 복잡도: O(n+m)

구현 코드

function solution(players, callings) {
  const map = new Map(players.map((name, index) => [name, index]));

  callings.forEach((name) => {
    const currentRank = map.get(name);
    const previousRank = currentRank - 1;

    [players[currentRank], players[previousRank]] = [players[previousRank], players[currentRank]];

    map.set(players[currentRank], currentRank);
    map.set(players[previousRank], previousRank);
  });

  return players;
}