■ 해결 방법
callings에 있는 값을 players에 순회해서 찾으려면 50,000 * 1,000,000의 시간복잡도가 소요된다.
따라서 O(n) 이하의 시간 복잡도로 풀 수 있는 방법을 찾아야 한다.
나는 players의 있는 값들을 순위를 매겨주었다.
{ mumu : 1, soe : 2, poe : 3, kai : 4, mine : 5} 이런식으로 해준 다음 callings에 불린 값과 그 앞의 값의 순서를 바꿔주는 형태로 진행했다. 이 때 주의해야 할 것은 players의 순서만 바꾸어 주는 것이 아닌, 순위도 값이 변경해주어야 하는 것이다.
■ 코드
function solution(players, callings) {
var answer = [];
let playersDict = []
let orderNum = 0;
for(let i = 0; i < players.length; i++){
playersDict[players[i]] = orderNum++;
}
for(let i = 0; i < callings.length; i++){
let tmpA = playersDict[callings[i]];
let tmp = players[playersDict[callings[i]]];
players[playersDict[callings[i]]] = players[playersDict[callings[i]] - 1];
players[playersDict[callings[i]] - 1] = tmp;
playersDict[ players[playersDict[callings[i]]]] = tmpA;
playersDict[callings[i]] = tmpA - 1;
}
return players;
}
728x90
'개발 > 알고리즘' 카테고리의 다른 글
프로그래머스_개인정보 수집 유효기간 (0) | 2024.05.02 |
---|---|
프로그래머스_[PCCP 기출문제] 1번 / 붕대 감기 (1) | 2024.05.01 |
프로그래머스_겹치는 선분의 길이 (0) | 2024.04.22 |
프로그래머스_평행 (0) | 2024.04.19 |
프로그래머스_구명보틀 (0) | 2021.08.26 |