문제
얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 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 : ["mumu", "soe", "poe", "kai", "mine"]
callings : ["kai", "kai", "mine", "mine"]
출력
["mumu", "kai", "mine", "soe", "poe"]
내가 했던 풀이 방법
-
indexOf를 이용하여 추월한 선수의 순위를 가져오고, 해당 순위 앞에 있는 사람과 swap해준다. -> 실패 (시간 초과) indexOf를 사용할 경우, O(n^2)이기 때문에 시간초과 발생.
-
player를 Map에 저장한 뒤, get을 이용하여 순위를 찾고 순위(value)를 1씩 줄이고 늘려줌 -> 실패 (시간초과) 문제를 풀기 위해서는 순위와 선수 이름의 값을 자유롭게 가져와야 하는데 value를 이용해서 key값을 가져오는 과정에서 시간초과 문제 발생.
-
player를 Map에 저장한 뒤, get을 이용해 순위를 찾고 players 배열을 이용해 앞 선수의 이름을 가져온다. 배열 디스트럭처링을 이용해 players 배열에서 값을 swap해주고, map에서 두 선수의 순위를 1씩 줄이거나 늘려준다. -> 성공
코드
function solution(players, callings) {
var answer = [];
let map = new Map();
players.forEach((name, index) => {
map.set(name, index);
})
let front = '';
let grade = 0;
for(let i=0; i<callings.length; i++) {
grade = map.get(callings[i]);
front = players[grade-1];
[players[grade-1], players[grade]] = [players[grade], players[grade-1]];
map.set(callings[i], map.get(callings[i])-1);
map.set(front, map.get(front)+1);
}
answer = players;
return answer;
}회고
시간초과를 해결을 못 해서 프로그래머스 문제 중에 제일 오래 시간 써서 푼 문제였던 것 같다. map을 사용하는 것까지는 생각해냈지만, map에서 value를 이용해서 key 값을 가져오는 부분에서 애를 먹었는데 겨우 구현했더니 또 시간초과... 결국 다른 사람들의 풀이를 참고해서 풀었다. 배열과 map을 동시에 활용하면 풀 수 있다는 점에 현타가 와다다다다... 왜 하나만 이용하려고 했을까.. 난 왜 편협한 생각에 사로잡혔을까....ㅎ 추가로 참고한 코드에서 디스트럭처링을 이용해 swap을 하는 코드를 보게 됐다. 디스트럭처링을 잠깐 들어본 적이 있었는데 swap할 때 정말 요긴하게 쓰일 것 같아서 기억해두어야겠다고 생각했다. 다음에 한 번 공부해서 정리해놔야겠다.
