달리기 경주

 

https://school.programmers.co.kr/learn/courses/30/lessons/178871

 

 아래의 코드는 시간 복잡도 O(N x M) 으로

   callings(N개의 배열) 내부의 요소수가 100만개이고.

   players(M개의 배열) 이 10개만 되어도

   M x N = 1000만 번의 연산을 수행 해야 한다.

function solution(players, callings) {
    for(let i=0; i<callings.length;i++){ // for 문으로 배열 전체 순회 해서 시간 복잡도 N
        const idx = players.indexOf(callings[i]) // indexOf 함수를 쓰게 되면 시간복잡도가 x M 만큼 증가
        players.splice(idx,1)
        players.splice(idx-1,0,callings[i])
    }
    return players
}



const players = ["mumu", "soe", "poe", "kai", "mine"]
const callings = ["kai", "kai", "mine", "mine"]
console.log(solution(players, callings)) //["mumu", "kai", "mine", "soe", "poe"]

 

 

 

문제점 

 1. 배열 순회 중첩으로 인한 높은 시간 복잡도 

 

해결방안

 1. 배열 순회는 1회로 시간 복잡도 O(N) 또는 O(M) 이 되게 한다.

 

구현 방법

  1. callings 만 1회 순회 시킨다.

  2. callings 의 요소로 players의 등수를 확인

    1) 이때 내부에 indexOf 매서드를 사용하면 전체 배열을 확인 해야 해서 중첩 for문과 동일한 역활을 하기 때문에 (X)

    2) 키 값으로 players의 등수를 확인 할 수 있게 객체로 관리한다.

       - callings의 요소로 players의 등수를 확인 가능

       - 자바스크립트 객체는 순서가 없기 때문에 바로 앞의 player 를 확인 할 수 없다.

         - 배열을 하나더 만들어서 object 의 rank 숫자에 맞게 배열의 순서를 관리 한다. (아래 참조)

const object = { name1 : rank1, name2 : rank2 .... }
const array = [ name1, name2, ..... ]

     3) rank1 의 숫자가 바뀌면 name1 의 배열의 위치도 rank1의 숫자에 맞게 이동한다.

     4) 마지막에 array를 반환

 

 

function solution(players, callings) {
  const object = {};
  players.forEach((el, idx) => {
    object[el] = idx;
  });

  for (let cp of callings) {
    const current = object[cp];
    const frontPlayer = players[current - 1];
    if (current === 0) {
      continue;
    }
    object[cp] -= 1;
    object[frontPlayer] += 1;
    [players[current - 1], players[current]] = [players[current],players[current - 1]];
  }
  return players;
}

 

 

< 추가 개선 >

앞의 플레이어와 객체값의 rank 를 바꾸는 것이기때문에 

object[cp] -= 1;
object[frontPlayer] += 1;

 

한줄로 구조 분해 할당으로 작성 가능하다.

   [object[cp], object[frontPlayer]] = [object[frontPlayer], object[cp]];