[프로그래머스 - JS] level.1 달리기 경주 ❗️

 

프로그래머스

---

나의 풀이 

쉬운줄 알고 바로 풀었는데 계속 시간초과가 났다.  

시간복잡도를 고려를 더 하고나서 풀자!

 

틀린 풀이 1

function solution(players, callings) {
  let newPlayers = [...players]
    for(let i = 0; i < callings.length; i++) {
      const tem = newPlayers.indexOf(callings[i])
      newPlayers = [...newPlayers.slice(0,tem), ...newPlayers.splice(tem+1)]
      newPlayers = [...newPlayers.splice(0,tem-1), callings[i], ...newPlayers]
  }
    return newPlayers
}

시간 복잡도가 O(n*(3m+k)) 이다. 

 

 

툴린 풀이 2

function solution(players, callings) {

    for(let i = 0; i<callings.length; i++){
        const callingPlayerIndex = players.indexOf(callings[i])
        const tem = players.splice(callingPlayerIndex, 1)
        players.splice(callingPlayerIndex - 1, 0, ...tem)
    }
    return players

}

시간 복잡도는 O(m*(n+n)) 으로 훨씬 더 커진다.  

 

정답 풀이

function solution(players, callings) {
    const dict = players.reduce((acc,cur,index) => {
       acc[cur] = index 
        return acc
    },{})
    
    callings.forEach((player) => {
        const curPlayerIndex = dict[player]
        
        // 앞선수
        const nextPlayer = players[curPlayerIndex - 1]
        
        
        // 자리교체
        players[curPlayerIndex - 1] = player
        players[curPlayerIndex] = nextPlayer
        
        // 객체 인덱스 순서도 변경
        dict[player] -= 1
        dict[nextPlayer] += 1
    })
    
    return players
}

다른 분 풀이를 참고해서 풀었다.  

 

최대한 시간복잡도를 줄여야 했다.  

위 코드의 시간 복잡도는 O(n+m)이라서 충분히 가능한 수치다.  

 

 

---