[프로그래머스] 달리기 경주

프로그래머스 LEVEL 1 - 달리기 경주

문제 이해하기

players와 callings 배열이 주어진다.

• players: 1등부터 현재 등수 순서대로 담긴 문자열 배열
• callings: 달리기 경주 도중 추월"한" 사람들의 이름이 들어있는 문자열 배열

 

문제를 보고 가장 먼저 든 생각은 callings 배열을 순회하면서 각 요소들의 index 값을 players 배열에서 찾은 뒤 splice를 이용해 바로 앞 위치에 해당 요소를 넣어주고 기존 위치의 값은 삭제하면서 players 배열을 갱신해주는 방식을 사용해야겠다는 생각이였다.

 

(이 생각 덕분에 열릴 지옥같은 미래는 생각도 못한채...)

 

아래와 같은 망한(?) 코드를 작성했다.

function solution(players, callings) {

    for (const name of callings) {
        players.splice(players.indexOf(name) - 1, 0, name);
        players.splice(players.indexOf(name) + 2, 1)
    }

    return players;
}

 

앞선 코드의 문제점

일단 문제를 자세히 보면 callings 배열의 길이가 최대 1,000,000이다.
근데 자바스크립트에서 indexOf()의 시간복잡도는 O(n)이라고 한다. 심지어 splice()의 시간복잡도도 O(n)이라고 한다.
callings의 요소가 최대 100만갠데 각 요소를 돌때마다 splice와 indexOf를 남발해댔으니 시간 초과가 뜰 수 밖에 없는 것은 자명한 사실이였다...

 

따라서 이를 개선하기 위한 방법을 곰곰이 생각해보았다.

1. indexOf 대신 해시맵을 이용해서 해당 요소의 위치에 빠르게 접근해야겠다.
2. 한 사람씩 추월하는데 굳이 splice를 쓸 필요 없이 앞 사람이랑 자리만 바꿔주면 되는게 아닌가.

결과적으로 아래와 같은 완성된 코드가 탄생하게 되었다.

 

시간 초과를 해결한 코드

function solution(players, callings) {
    // 1. 선수들의 초기 순서를 해시맵에 미리 저장해둔다.
    const indexList = new Map()

    for (let i = 0; i < players.length; i++ ) {
        indexList.set(players[i], i)
    }

    for (const name of callings) {
        // 2. 추월한 사람(불린 사람)과 추월 당한 사람을 각각 called, passed 변수에 저장한다.
        const called = name
        const passed = players[indexList.get(name) - 1]

        // 3. 추월한 사람과 추월된 사람의 위치를 서로 바꿔준다.
        const temp = players[indexList.get(called) - 1]
        players[indexList.get(called) - 1] = players[indexList.get(called)];
        players[indexList.get(called)] = temp;

        // 4. 선수들의 순서가 바뀌었으니 기존 해시맵의 순서도 갱신해줘야한다.
        indexList.set(called, indexList.get(called) - 1)
        indexList.set(passed, indexList.get(passed) + 1)
    }

    // 최종 결과를 반환한다.
    return players;
}