코딩테스트 Lv1 - 달리기 경주

첫 번째 코드

function solution(players, callings) {
  function swap(x){
      const xIndex = players.indexOf(x)
      const target = players[xIndex]
      const deTarget = players[xIndex-1]
      players[xIndex]=deTarget
      players[xIndex-1]=target
  }
    callings.forEach((player)=>swap(player))
    
    return players
    
}

결과: 시간초과

callings의 크기가 최대 1,000,000이다. 그럼 위 callings를 순회하며 players의 배열을 직접 수정하는 작업은 시간초과를 유발하는 것으로 보인다.

그럼 players의 배열을 수정하지 않고 결과를 도출하는 방법을 찾아본다.

두 번째 코드: hash를 이용

function solution(players, callings) {
    
    let hash = new Map()
    players.forEach((player,i)=>{
        hash.set(player,[i+1,players[i-1],players[i+1]])
    })

    callings.forEach((call,i)=>{
     const [grade,front,back] = hash.get(call)
     hash.set(call,[grade-1,hash.get(front)[1],front])
     hash.set(front,[grade,call,back])
     if(back){
         hash.set(back,[grade+1,front,hash.get(back)[2]])
     }
        
    })
    hash=[...hash]
    hash.sort((a,b)=>a[1][0]-b[1][0])
    
    hash=hash.map((item,index)=>item[0])
    return hash

}

hash를 이용해 등수, 앞, 뒤 정보를 입력해주고 이를 스왑해주는형식으로
구현을 해보았다.

결과: 시간초과 및 오류

오히려 더 점수가 낮게 나왔다. 정확도가 떨어지는 것으로 예상된다.
여기서 구글링을 통해 어떤 요소가 시간초과를 유발했을지 찾아보았다.

문제는 indexOf메소드였다. 해당 메소드는 n^2의 연산을 한다고한다.

그럼 index를 바로 찾을 수 있게 Hash로 index를 관리하면되지 않을까

세 번째 코드

function solution(players, callings) {
 const obj = {}
 
 players.forEach((player,index)=>obj[player]=index)
    
 callings.forEach((call,i)=>{
     const index = obj[call]
     const frontIndex=index-1

     players[index]=players[index-1]
     players[frontIndex]=call
     
     obj[call]=obj[call]-1
     obj[players[index]] = obj[players[index]]+1
     
     
 })   
    return players
    
  
}

index를 object로 관리하고 indexOf메서드 없이 해당 index(순서)를 찾아 수정할 수 있도록했다.

결과: 통과