달리기 경주

하늘·2024년 4월 26일

프로그래머스

목록 보기

2/3

이 문제는 문제 그대로 작성하면 되는 간단한 문제긴 한데 제한 사항이 복병이다.

내 풀이

해설진에게 불린 선수(callings) 는 앞 선수를 추월했다는 뜻(=순위 + 1)
players에서 불린 선수의 이름 순번을 찾고 구조분해할당으로 앞 선수와 순서를 바꿔주었다.

    callings.forEach((item, i) => {
        let index = players.indexOf(item);
        [players[index - 1], players[index]] = [players[index], players[index - 1]]
    })

    return players

그냥 이렇게 하면 코드는 간단하지만 통과가 안된다.

[질문하기]를 통해 이유를 알아보니
제한사항에서 callings의 원소 길이가 1백만, players의 길이가 5만으로 반복 수행시 작업 횟수가 어마어마하다.
= 요컨대 효율적으로 처리해야한다는 것

제한 사항

5 ≤ players의 길이 ≤ 50,000
players[i]는 i번째 선수의 이름을 의미합니다.
players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
players에는 중복된 값이 들어가 있지 않습니다.
3 ≤ players[i]의 길이 ≤ 10
2 ≤ callings의 길이 ≤ 1,000,000
callings는 players의 원소들로만 이루어져 있습니다.
경주 진행중 1등인 선수의 이름은 불리지 않습니다.

힌트

[질문하기]의 힌트 : 이름별 index를 object로 만들기

그러게요.... 생각해보니까 지금은 indexOf가 forEach 내부에 있어서 5만x1백만 번의 연산을 해야하지만
나눠서 하면 5만+1백만번의 연산으로 줄일 수 있다.

indexOf에 대한 고찰 글을 보니

자바스크립트에서 indexOf 메소드를 사용하여 배열 내에서 특정 요소를 찾는 경우, 이 메소드는 선형 검색 알고리즘을 사용하기 때문에(배열의 처음부터 끝까지 순차적으로 요소를 하나씩 확인하며 찾고자 하는 요소를 검색함) 이 과정의 시간복잡도는 O(n)으로 배열의 길이가 길어질수록 검색 시간이 비례하여 증가한다.

따라서 address 개념인 object를 활용하라는 힌트는
객체를 이용해 데이터를 저장하고 접근하여 특정 키로 값에 접근하기 때문에
시간복잡도가 O(1)이어서 데이터 양에 관계없이 상수 시간 내에 접근이 가능하다고 한다.
즉 큰 데이터 세트를 다룰때 매우 효율적이라는 것!!
[참고 링크] https://hwani.dev/js-indexOf/

그냥 풀면 되는 줄 알았더니 알고리즘 공부를 병행해야하는구나
근데 중고등학교 수학 개념이랑 같아서 재밌는거같음

재풀이

대박깔쌈하고멋진 workkhw97@gmail.com님의 풀이를 참고함
포인트는 원본 players array를 변경하는게 아닌 참고 객체를 변경하는 것!

1. 키:값 쌍으로 데이터를 객체에 저장한다.

const keyPlayers = {}
const keyRanks = {}

    players.forEach((player, idx) => {
        const rank = idx + 1;
        keyPlayers[player] = rank
        keyRanks[rank] = player
    })

// keyPlayers = { mumu: 1, soe: 2 ... }
// keyRanks = { '1': 'mumu', '2': 'soe' ... }

keyPlayers는 player : rank이고
keyRanks는 rank : player이다.

2. callings를 순회하며 참고 객체를 변경한다.

allings.forEach((calling) => {
        const losePlayer = keyRanks[keyPlayers[calling] - 1];

        // 추월한 선수와 불린 선수 값 변경
        keyRanks[keyPlayers[calling]] = losePlayer;
        keyRanks[keyPlayers[losePlayer]] = calling;

        // 순위 업데이트
        keyPlayers[calling] -= 1;
        keyPlayers[losePlayer] += 1;
    })