[프로그래머스] 달리기 경주(Lv1, js)

문제 자체는 단순하다.
하지만 제한 조건이 커지자마자 코드가 비명을 질렀고, 결국 효율적인 구조로 다시 짜야 했다.
그 과정을 정리해보려 한다.

문제 개요

달리기 경주가 열리고, 선수들이 1등부터 N등까지 줄을 서 있다.

해설진이 특정 선수의 이름을 부르면, 그 선수는 앞사람과 자리를 바꾼다.

• 선수 이름 배열: players (현재 순위 순)
• 호출 배열: callings (선수 이름만 있음)
• 매 호출마다 해당 선수는 앞으로 한 칸 이동
• 모든 호출이 끝난 뒤의 최종 순위를 구하는 문제다.

1차 시도: 단순 구현

처음에는 별생각 없이 이렇게 풀었다.

function solution(players, callings) {
  for (let name of callings) {
    const idx = players.findIndex(p => p === name);
    [players[idx - 1], players[idx]] = [players[idx], players[idx - 1]];
  }
  return players;
}

• findIndex로 이름을 찾아서
• 앞 사람이랑 swap만 해주면 끝이다!

특정 테스트 케이스에서 시간 초과가 나버렸다.

원인파악

분석해보니 원인은 명확했다.

• callings.length는 최대 1,000,000

• players.findIndex(...)는 최악의 경우 O(N)

  → 전체 시간복잡도는 O(C × N) = 5천억.

BFS가 아니어서 다행이지, 이건 그냥 선형 탐색 지옥이었다.

해결 : 선수 이름을 맵으로 관리

어떻게든 findIndex를 없애야 했다.

그래서 선수 이름 → 현재 인덱스를 Map으로 관리하기로 했다.

const nameToIndex = new Map();
players.forEach((name, idx) => nameToIndex.set(name, idx));

그리고 호출마다:

• 선수 이름으로 인덱스를 O(1)에 얻고
• players 배열과 Map을 동시에 업데이트

🚀 최적 코드

function solution(players, callings) {
  const nameToIndex = new Map();

  players.forEach((name, i) => nameToIndex.set(name, i));

  for (let name of callings) {
    const idx = nameToIndex.get(name);

    // swap in array
    const frontPlayer = players[idx - 1];
    players[idx - 1] = name;
    players[idx] = frontPlayer;

    // update map
    nameToIndex.set(name, idx - 1);
    nameToIndex.set(frontPlayer, idx);
  }

  return players;
}

시간복잡도 비교

구현 방식	시간복잡도	통과 여부
findIndex 사용	O(C × N)	❌ 시간 초과
Map 활용	O(N + C)	✅ 통과

정리하며

이 문제는 알고리즘보다도 자료구조 선택의 중요성을 다시금 느끼게 해줬다.

• 해시(Map)는 단순히 빠른 접근만이 아니라, 불필요한 반복을 없애는 구조 설계에도 핵심이었다.
• 또한 배열을 swap할 때는 양쪽 데이터 모두를 갱신해야 한다는 점도 함께 다뤘다.

교훈

✅ findIndex는 편하지만 느리다

✅ 대규모 탐색에는 반드시 Map을 고려하자

시간복잡도... 진짜 사전에 고려하자.