[PS/JS] 프로그래머스 - 달리기 경주

Pakxe·2023년 4월 8일

JavaScript ps 프로그래머스

PS

목록 보기

4/16

문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/178871

풀이

3번에 걸쳐 풀이를 생각했으므로 답이 궁금하다면 3차 시도 (성공)으로 가서 보자.

일단 입력 배열인 players, callings의 크기가 각각 50000, 1000000 이므로 시간초과가 날 수 있다는 생각을 갖고 시작했다. (알아도 틀림 ㅜ)

1차 시도 (실패)

처음 생각한 풀이는, players에 순위를 달아주는 방법이었다.

players를 map 메서드를 이용해[[1, 'park'], [2, 'se'], [3, 'hyun']] 로 만들기

callings를 하나씩 읽으면서 추월자 이름을 1에서 만든 배열에서 indexOf로 찾아 순위를 바꾼다.

2에서 구한 추월자의 순위를 이용해 추월당하는 자의 이름을 indexOf로 찾아, 이 사람의 순위를 바꾼다.

당연하게도 시간초과가 났다. 배열에서 간단하게 이름을 찾기위해 indexOf라는 연산자를 사용했는데, 이렇게되면 2번, 3번 두 번을 indexOf로 찾아야한다.
그런데 indexOf는 시간복잡도가 O(n)이다. 따라서 시간이 50000 * 1000000 * 1000000(indexOf) * 1000000(indexOf) 가 되어 실행 시간이 굉장히 증가한다. 당연히 시간초과가 날 수 밖에 없다.

2차 시도 (실패)

두번째로 생각한 풀이는 map을 사용하는 것이다. players에는 중복된 값이 들어있지 않다고 했으니까 players에 있는 이름을 key값으로 하고 value를 순위로 하는 것이다.

map을 사용하면 배열에서 요소를 찾는 방법인 indexOf같은 시간이 많이 드는(O(n)) 메서드를 사용하지 않아도 된다. 왜냐면 map에는 get이라는 시간복잡도가 O(1)인 메서드가 있기 때문이다. 따라서 이를 이용해 풀이를 생각해보면 아래와 같다.

맵을 선언하고 players를 forEach로 돌며 이름을 key로 하고 순위를 value로 한 요소들을 map에 추가한다.

callings를 하나씩 읽으면서 추월자의 순위를 map.get(name)으로 찾는다.

추월자의 순위를 -1 로 해서 map에 갱신한다.

추월자의 순위 - 1를 이용해 추월당하는자의 이름을 map에서 찾는다. 이때 for문을 사용하기 때문에 시간복잡도가 O(n)이 추가된다. (value 로 key값을 찾는 메서드는 map에 없다..)

추월당하는 자의 순위를 추월자의 원래 순위로 갱신한다.

다만 이렇게되면 여전히 value인 순위를 찾을 때 여전히 많은 시간이 소요된다. 그래서 실패했다.

3차 시도 (성공)

이건 새로 알게된 방법이다. 원래는 이름을 key로 하고 순위를 value로 하는 맵을 사용했었다. 하지만 그렇게되면 순위를 이용해 이름을 찾을 때 여전히 시간이 많이 걸린다고 했다.

그러니 순위를 key로 하고 이름을 value로 하는 map도 사용하면 됐다! 맵을 총 2개 사용하는 것이다.

이렇게 하면 value인 순위로 이름을 찾을 때 하나씩 순회하며 찾는 것이 아닌 시간이 짧은 map.get으로 찾을 수 있기 때문에 시간초과가 안날 가능성이 높다.

그렇게 생각한 풀이는 아래와 같다.

맵을 두개 선언하고 이름을 키로 하는 맵, 순위를 키로 하는 맵 두 개를 만든다. (forEach로 돌며..)

callings를 하나씩 읽으며 추월자의 순위를 get으로 찾는다.

찾은 추월자의 순위 - 1로 추월당하는자의 이름을 get으로 찾는다. (이제 알고있는건 추월자 이름, 추월당하는자의 이름, 추월자의 순위)

추월당하는자의 순위를 추월자의 순위로 set한다. (이름을 key로하는 맵)

추월자의 순위를 추월자의 순위 - 1로 set한다. (이름을 key로하는 맵)

추월자의 순위를 추월당하는 자의 이름으로 set한다. (순위를 key로 하는 맵)

추월자의 순위 -1 를 추월자의 이름으로 set한다. (순위를 key로 하는 맵)

답이 맞았으므로 아래에 코드를 첨부한다. 주석에 적힌 숫자가 위 풀이의 번호이다.
영어 변수명이 길어질 것 같아서 직관적인 한글 변수명을 사용해 코드를 작성했다 (ㅜㅜ)

정답 코드

function solution(players, callings) {
    const nameKeyMap = new Map();
    const scoreKeyMap = new Map();
    
    players.forEach((player, i) => { // 1
        nameKeyMap.set(player, i);
        scoreKeyMap.set(i, player);
    }) 
    
    callings.forEach((추월자) => { // 2
        const 추월자의순위 = nameKeyMap.get(추월자); // 2
        const 추월당할자의이름 = scoreKeyMap.get(추월자의순위 - 1); // 3
        
        nameKeyMap.set(추월당할자의이름, 추월자의순위); // 4
        nameKeyMap.set(추월자, 추월자의순위 - 1); // 5
        
        scoreKeyMap.set(추월자의순위, 추월당할자의이름); // 6
        scoreKeyMap.set(추월자의순위 - 1, 추월자); // 7
    })
    
    const scoreArr = Array.from(scoreKeyMap); // sort하기위해 map을 배열로 변환
    
    scoreArr.sort((a, b) => a[0] - b[0]); // 순위 오름차순으로 sort
    
    return scoreArr.map(([_, name]) => name); // 이름만 return
}