[알고리즘] 달리기 경주 (해시)

1. 조건

배열 `players` 의 최대 길이 50,000

배열 `callings` 의 최대 길이 1,000,000

 

2. 과정

`callings`을 최대 1,000,000 순회하면서

`players`에서 해당 문자열의 index찾고 업데이트 해야한다.

 

POINT

선형 탐색을 할 경우 최대 1,000,000 * 50,000 (= 500억)의 리소스가 소모된다.

(시간 초과되는것이 당연.)

 

해시 테이블을 최대 50,000의 리소스를 이용해서 먼저 만들어 준다면

`callings`의 길이만큼 `players`를 순회할 필요 없이

N(1)로 해당 Index를 바로 찾아낼 수있다.

 

3. 풀이

function solution(players, callings) {
  // ojb로 player: idx로 복사
  const obj = {};
  for (let idx = 0; idx < players.length; idx += 1) {
    obj[players[idx]] = idx;
  }

  for (let idx = 0; idx < callings.length; idx += 1) {
    // playerIdx에 호명된 선수 idx 선언
    const calledPlayerIdx = obj[callings[idx]];

    // players 배열 업데이트
    const temp = players[calledPlayerIdx - 1];
    players[calledPlayerIdx - 1] = players[calledPlayerIdx];
    players[calledPlayerIdx] = temp;

    // obj 객체 업데이트
    obj[temp] = calledPlayerIdx;
    obj[callings[idx]] = calledPlayerIdx - 1;
  }

  return players;
}