[프로그래머스] Level1 - 달리기 경주(Javascript)

프로그래머스

한 달 반만에 알고리즘을 풀어서 감이 떨어졌을 것이라고 판단해서 레벨 1의 난이도를 풀었다. 

▶️▶️ 문제 요약

1️⃣ 해설진은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부른다.

2️⃣ 1 ~ 3등까지의 선수 중에서 2등선수를 부르면 1등이랑 바뀐다.

3️⃣ 경주가 끝이나면 1등부터 등수 순서대로 배열에 담는다. 

 

❌ 실패 코드

function solution(players, callings) {
    let answer = [];
    let orders = {};
    
    for (let c = 0; c < callings.length; c++) {
        let order = players.indexOf(callings[c])
        let temp = players[order-1];
        players[order-1] = players[order];
        players[order] = temp
    }
    return players
}

 

❗️실패 이유

 

👉 처음에 정답이 통과하길래 문제가 없는 줄 알았는데.. callings 배열의 길이가 1,000,000개 이하라서 시간초과가 뜬다. 자세히보면 indexOf메서드가 배열을 처음부터 끝까지 순회하며 해당 요소를 찾아야하기 때문에 시간 복잡도는 (players길이 * callings의 길이)이기 때문에 매우 느리고 오래걸린다.

👉 원래는 선수들의 순서를 저장해놓기 위해서 객체에 선수이름과, 순서를 저장해 놓았는데 indexOf()메서드가 있어서 되는 줄 알고 안 썼는데 안 쓴 거를 후회한다..

 

 

✅ 정답 코드

function solution(players, callings) {
    let answer = [];
    let orders = {};
    
    // 플레이어의 순서를 객체에 담는다.
    for (let i = 0; i < players.length; i++) {
        orders[players[i]] = i;
    }

    
    
    for (let c = 0; c < callings.length; c++) {
        // 호출된 이름의 순서 
        let order = orders[callings[c]];
        
        
        // 플레이어의 위치를 바꿔준다.
        // 앞과 뒤의 플레이어 
        let temp = players[order-1]
        players[order-1] = players[order]
        players[order] = temp
        
        
        // 객체도 그에 맞게 업데이트를 진행해야한다.
        
        // 뒤로 순서가 밀린 (ex => 2등 -> 3등)
        orders[players[order]] = order;
        // 순서가 올라감 (ex => 3등 -> 2등)
        orders[players[order-1]] = order-1;
    }
    return players
}

👉 객체를 사용하면 O(1)의 시간복잡도로 빠르게 선수들을 찾아낼 수 있다는 것을 알게 됐다. 

👉 이전 코드와 비교하자면 똑같은 부분은 플레이어의 순서를 바꿔주는 로직은 똑같지만 객체에 담긴 순서들도 업데이트 해주는 게 차이점이다. 이게 업데이트가 되어야 다음에 해당 플레이어의 위치를 정확히 찾아낼 수 있다. 

 

 

📝 느낀점

 

👉 오랜만에 알고리즘을 푸는 거라 감이 많이 떨어졌을 것이라고 생각해서 걱정이 꽤 됐었는데, 문제를 요약하고, 수도코드를 작성하면서 푸니까 도움이 많이 됐다. 그리고 역시 시간복잡도를 고려해서 코드를 짜야한다.