[프로그래머스] 연습문제 / 달리기 경주 / Lv1 / JS / 접근법

 

---

문제 설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

---

제한사항

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

입출력 예

 

players	callings	result
["mumu", "soe", "poe", "kai", "mine"]	["kai", "kai", "mine", "mine"]	["mumu", "kai", "mine", "soe", "poe"]

 

입출력 예 설명

입출력 예 #1

• 4등인 "kai" 선수가 2번 추월하여 2등이 되고 앞서 3등, 2등인 "poe", "soe" 선수는 4등, 3등이 됩니다.
• 5등인 "mine" 선수가 2번 추월하여 4등, 3등인 "poe", "soe" 선수가 5등, 4등이 되고 경주가 끝납니다.
• 1등부터 배열에 담으면 ["mumu", "kai", "mine", "soe", "poe"]이 됩니다.

나의 접근 방법

1. 현재 순서인 players 배열을 가지고 callings를 순차적으로 순회하면서 체크

2. players에서 불리는 이름의 선수이름을 가지고 indexOf로 index를 찾아서 앞에 선수와 변경

나의 JS 코드

function switchPlayer(arr, a){
    if(arr.indexOf(a) > -1 ){
        const idx = arr.indexOf(a);
        [arr[idx], arr[idx-1]] = [arr[idx-1],arr[idx]]
    }
}
function solution(players, callings) {
    var answer = [];
    
    for(let i=0; i<callings.length; i++){
        switchPlayer(players, callings[i])
    }
    
    
    return players;
}

개선할 포인트

1. 문제의 병목 분석

• arr.indexOf(a)가 병목입니다. 이 함수는 호출될 때마다 배열을 순차적으로 검색하므로 **O(n)**의 시간이 걸립니다.
• callings의 길이만큼 반복되므로 전체 시간 복잡도는 **O(n * m)**이 됩니다.

2. 최적화 아이디어

배열에서의 검색 속도를 개선하기 위해 데이터를 효율적으로 관리하는 자료구조를 활용해야 합니다.

핵심 아이디어

1. Map 자료구조를 사용하여 각 선수의 현재 인덱스를 빠르게 조회할 수 있도록 합니다.
   • Map은 키-값 쌍으로 이루어져 있고, 조회와 업데이트가 **O(1)**에 가능합니다.
2. players 배열은 그대로 두고, 각 호출에 따라 인덱스만 업데이트합니다.
   • indexMap을 유지하여 현재 각 플레이어의 위치를 저장합니다.

 

개선 된 코드

 

function solution(players, callings) {
    var answer = [];
    let map = new Map();
    
    players.forEach((player,i) => map.set(player,i))
    
    for(let i=0; i<callings.length; i++){
        const index = map.get(callings[i]);
        
        map.set(callings[i], index-1);
        map.set(players[index-1], index);
        
        if(index >= 0 )
            [players[index],players[index-1]]=[players[index-1],players[index]];
    }

    return players;
}

속도 체크

개선전 O(n * m)  => 개선 후 O(n + m)

 

	개선 전	개선 후
테스트 1 〉	통과 (0.07ms, 33.4MB)	통과 (0.08ms, 33.5MB)
테스트 2 〉	통과 (0.16ms, 33.4MB)	통과 (0.09ms, 33.4MB)
테스트 3 〉	통과 (0.24ms, 33.5MB)	통과 (0.24ms, 33.6MB)
테스트 4 〉	통과 (1.17ms, 33.7MB)	통과 (0.63ms, 33.7MB)
테스트 5 〉	통과 (48.22ms, 37.6MB)	통과 (6.41ms, 37.7MB)
테스트 6 〉	통과 (33.97ms, 36.8MB)	통과 (10.47ms, 38MB)
테스트 7 〉	통과 (799.39ms, 40.4MB)	통과 (11.37ms, 41.7MB)
테스트 8 〉	통과 (3110.40ms, 45.1MB)	통과 (22.62ms, 46MB)
테스트 9 〉	실패 (시간 초과)	통과 (30.62ms, 50.8MB)
테스트 10 〉	실패 (시간 초과)	통과 (89.61ms, 70MB)
테스트 11 〉	실패 (시간 초과)	통과 (203.44ms, 84MB)
테스트 12 〉	실패 (시간 초과)	통과 (191.70ms, 84MB)
테스트 13 〉	실패 (시간 초과)	통과 (271.27ms, 84MB)
테스트 14 〉	통과 (0.08ms, 33.4MB)	통과 (0.10ms, 33.5MB)
테스트 15 〉	통과 (0.07ms, 33.4MB)	통과 (0.10ms, 33.4MB)
테스트 16 〉	통과 (0.16ms, 33.4MB)	통과 (0.17ms, 33.5MB)