달리기 경주

 

 

function solution(players, callings) {
	//rank배열 생성
    let rank = [...players]
    //callings의 요소들을 돌면서 해당 순서의 값의 위치를 찾아내
    //앞 등수의 이름을 저장해두고, call요소를 앞으로 보내고 저장해둔 앞 등수의 이름을
    //call의 등수였던 곳으로 바꿀 생각이다.
    for (let call of callings) {
        let presentCallRank = rank.indexOf(call)
        let aboveRankName = rank[presentCallRank-1]
        rank[presentCallRank-1] = call
        rank[presentCallRank] = aboveRankName
    }
    //바뀌어진 rank배열을 리턴한다.
    return rank;
}

아마 players배열의 크기가 커지면서 indexOf가 필요로하는 시간이 매우 커져 실패한 것으로 생각한다.

 

function solution(players, callings) {
	//rankArr배열을 만들어 준다.
    let rankArr = [...players]
    //시간복잡도를 낮추기 위해 Map객체를 사용한다.
    let rankMap = new Map();
    
    //players배열, 순위를 rankMap에 세팅한다.
    players.forEach((name, index) => {
        rankMap.set(name, index)
    })
    
    //callings배열의 각 call마다 위치를 변경해준다.
    for (let call of callings) {
    	//rankMap에 저장되어있는 call의 순위를 가져온다.
        let presentRank = rankMap.get(call)
        //call의 앞 순위 이름을 rankArr에서 가져온다.
        let front = rankArr[presentRank-1]
        //call의 앞 순위 등수를 변수로 저장해둔다. (직관적으로 해석가능하게)
        let frontRank = presentRank-1
        //rankArr의 앞 순위를 call로 바꿔주고
        //rankArr의 현재 순위를 앞 순위였던 이름으로 바꿔준다.
        rankArr[frontRank] = call
        rankArr[presentRank] = front
        //rankMap의 각 이름의 순위를 변경해준다.
        rankMap.set(call, frontRank)
        rankMap.set(front, presentRank)
    }
    
    return rankArr;
}

반복마다 O(N*N0)이었던 시간복잡도가 O(N)로 바뀌면서 시간초과 실패를 해결하였다.