프로그래머스 문제풀이

달리기 경주

시도

처음에는 단순히 callings 배열을 순회하며 players.indexOf로 찾은 index의 값을 앞의 값과 swap하는 방법으로 진행했다.

그러면 결국 players는 순위가 원하는대로 정렬이 된다.

문제 (시간 초과)

내가 구현한 로직은 최악의 경우, 즉 callings에 100만 개의 요소가 들어있고 players에 5만 개의 요소가 들어있으며 callings의 모든 요소가 players의 마지막 요소와 같은 경우, 100만 개를 순회하며 5만 번을 탐색(총 50억 개의 연산)하게 된다.
프로그래머스에서 시간 초과가 뜨는 정확한 기준? 수치?는 모르겠지만 어쨌든 위 방법은 굉장히 오래 걸리는, 비효율적인 방법이다.

해결 방법

1. players 배열을 이용해 2개의 map 객체 (1. 순위:이름, 2. 이름:순위) 생성.
2. 이름:순위 map에서 call(key)을 이용해 player의 순위(value)를 찾을 수 있는데, call이 추월을 했으므로 newRank에 (현재 순위 - 1)을 저장.
3. 순위:이름 map의 기존 newRank에 있던 player(추월당한 선수)을 preName에 저장.
4. 순위:이름 map의 newRank 자리(key)에 call(value)을 넣어주고 newRank+1 자리(key)에 preName(value)을 저장. (swap)
5. 이름:순위 map에도 4번과 마찬가지로 swap.
6. 반복문을 마쳤을 때 순위:이름 map에는 모든 선수들의 최종 순위가 담겨져 있으므로 map의 이름(value)값만 추출한 배열을 반환.

const solution = (players, callings) => {
  let playerMap = new Map();
  let rankMap = new Map();
  let newRank, preName;
  // 1
  players.map((player, ranking) => playerMap.set(player, ranking + 1));
  // 1
  players.map((player, ranking) => rankMap.set(ranking + 1, player));

  callings.map((call) => {
    // 2
    newRank = playerMap.get(call) - 1;
    // 3
    preName = rankMap.get(newRank);
    
    // 4
    rankMap.set(newRank, call);
    rankMap.set(newRank + 1, preName);

    // 5
    playerMap.set(call, newRank);
    playerMap.set(preName, newRank + 1);
  });
  // 6
  return Array.from(rankMap.values());
};

배운 점 / 느낀 점

처음에는 어떻게 이 문제를 반복문 없이 풀지라는 생각만 하다가 도저히 안되겠어서 슬랙에 질문을 올리니까 map 객체를 사용하여 풀면 된다는 도움을 받았다.
C, C++만 오래 배우기도 했고 JavaScript가 생소하다 보니 생각이 안 났었다.
map 객체를 이용한 방법이 배열을 이용한 방법보다 빠른 이유:

• players 배열에서 callings의 각 요소를 찾을 때 indexOf를 사용하면 결국 0번째부터 끝까지 순회하면서 요소를 검색하는 것이기 때문에 이번 문제에서 최악의 경우 5만 번 순회를 함.
• 반면 map에는 요소들이 key:value 짝으로 저장이 되기 때문에 key값을 이용해 원하는 value값을 바로 찾을 수 있음. 최악의 경우(찾는 이름이 배열의 49999번째 요소인 경우)

Array.prototype.indexOf() vs Map.prototype.get()

let arr = [];
for (let i = 0; i < 50000; i++) arr.push(i);
let map = new Map();
arr.map((ele, i) => map.set(ele, i));

console.time("Array.indexOf()를 이용해 49999의 인덱스 찾기: ");
for (let i = 0; i < 10; i++) arr.indexOf(49999);
console.timeEnd("Array.indexOf()를 이용해 49999의 인덱스 찾기: ");

console.time("map.get()을 이용해 49999의 인덱스 찾기: ");
for (let i = 0; i < 10; i++) map.get(49999);
console.timeEnd("map.get()을 이용해 49999의 인덱스 찾기: ");

얼마나 차이가 큰 지 확인해보고 싶어서 코드를 작성했다.

위 코드는 50000개 크기의 배열과 맵을 만들어 각각에 indexOf와 get 호출을 통해 마지막 요소의 탐색을 10번 반복하는 데 걸리는 시간을 출력하는 코드이다.

위 코드를 20번 실행했을 때 평균 소요시간이 각각 0.29ms, 0.03ms으로 get을 썼을 때 훨씬 시간이 절약된다는 걸 알았고,

위 코드에서 탐색을 10번이 아닌 1000000번 반복을 했을 때 소요시간은 각각 653.31ms, 3.74로 get을 쓰는 게 훨씬 빠르다는 것을 알 수 있다.

특히 반복 횟수가 늘면 늘수록 두 시간값의 차이도 엄청 벌어진다는 것을 알 수 있다.

+추가 (2023.04.08)

위의 indexOf와 get의 실행 시간을 비교하는 코드에서 console.time, console.timeEnd보다 process.hrtime으로 찍는게 더 정확한 것 같다고 느껴서 아래 수정본을 추가했다.

let arr = [];
for (let i = 0; i < 50000; i++) arr.push(i);
let map = new Map();
arr.map((ele, i) => map.set(ele, i));

const startTime1 = process.hrtime();
for (let i = 0; i < 50000; i++) arr.indexOf(49999);
const endTime1 = process.hrtime(startTime1);
console.log(`indexOf 실행 시간: ${endTime1[0]}.${endTime1[1]}ms`);

const startTime2 = process.hrtime();
for (let i = 0; i < 50000; i++) map.get(49999);
const endTime2 = process.hrtime(startTime2);
console.log(`get 실행 시간: ${endTime2[0]}.${endTime2[1]}ms`);

위 코드를 10회 실행하면 indexOf는 0.79ms, get은 0.11ms 정도로 get이 훨씬 적게 걸린다는 것을 볼 수 있다.

근데 avg1, avg2에 실행 시간들(100번)을 누적해서 평균값을 출력해봤는데

let arr = [];
for (let i = 0; i < 50000; i++) arr.push(i);
let map = new Map();
arr.map((ele, i) => map.set(ele, i));

let arr1 = [];
let arr2 = [];

let getAverage = function (arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) sum += arr[i];
  return sum / arr.length;
};

for (let a = 0; a < 100; a++) {
  const startTime1 = process.hrtime();
  for (let i = 0; i < 50000; i++) arr.indexOf(49999);
  const endTime1 = process.hrtime(startTime1);
  arr1.push(parseFloat(`${endTime1[0]}.${endTime1[1]}`));
  console.log(`indexOf 실행 시간: ${arr1[a]}ms`);

  const startTime2 = process.hrtime();
  for (let i = 0; i < 50000; i++) map.get(49999);
  const endTime2 = process.hrtime(startTime2);
  arr2.push(parseFloat(`${endTime2[0]}.${endTime2[1]}`));
  console.log(`get 실행 시간: ${arr2[a]}ms`);
}

console.log(getAverage(arr1));
console.log(getAverage(arr2));

4번 째 출력부터는 get의 실행시간이 indexOf의 실행 시간보다 더 길어진다.. 왜일까..?