[JS] 달리기 경주

문제 소개

프로그래머스 코딩테스트 연습 : [Level 1] 달리기 경주

 

 

자료구조/알고리즘, 시간복잡도, 소요시간

• 자료구조/알고리즘: Hash
• 시간 복잡도: O(n)
• 소요 시간: 45분

 

 

코드

function solution(players, callings) {
    let playersDict = {}
    let playersRankDict = {}
    
    players.forEach((player, index) => {
        playersDict[player] = index;
        playersRankDict[index] = player;
    })
    
    callings.forEach((calling) => {
        let rankupPlayer = calling;
        let rankupPlayerRank = playersDict[calling];
        let rankdownPlayerRank = rankupPlayerRank - 1;
        let rankdownPlayer = playersRankDict[rankdownPlayerRank];
        
        playersDict[rankupPlayer] = rankupPlayerRank - 1;
        playersDict[rankdownPlayer] = rankdownPlayerRank + 1;
        playersRankDict[rankupPlayerRank] = rankdownPlayer;
        playersRankDict[rankdownPlayerRank] = rankupPlayer;
    })
    
    return Object.values(playersRankDict)
}

 

 

회고

문제를 처음 접했을 때는 calling.forEach(() => {indexOf}) 를 활용한 O(N^2)의 알고리즘을 구현했다.

Level 1이라서 쉽게 본것도 있었고 보자마자 해당 알고리즘이 바로 떠올랐지만, 4개의 케이스에서 시간 초과로 해결하지 못했다.

그때부터 짧게 고민할 수 있었던 문제에 대해 많은 시간을 소모한 것 같아서 아쉬웠다.

 

놓친 개념

배열보다 해시(객체)가 탐색, 수정, 삽입 연산이 훨씬 빠르다!! (알고 있었는데,, 첫 알고리즘이 틀리니까 많이 헤매었던 것 같다)