달리기 경주
https://school.programmers.co.kr/learn/courses/30/lessons/178871
코드
function solution(players, callings) {
const answer = {};
players.forEach((v,i)=>{
answer[v] = (answer[v] || 0) + i;
})
callings.forEach((v)=>{
const [prevIdx, callIdx] = [answer[v]-1, answer[v]];
answer[players[prevIdx]] = callIdx;
answer[v] = prevIdx;
players[callIdx] = players[prevIdx];
players[prevIdx] = v;
})
return Object.entries(answer).sort((a, b)=> a[1] - b[1]).map((v)=>v[0]);
}풀이
처음에는 forEach로 callings를 순회하면서 players에서 요소의 idx를 뽑아내 이전 요소와 교환하면 되겠다고 생각했다. 하지만 몇몇 테스트에서 시간 초과되었다. 이유를 찾아보니 시간 복잡도에 걸렸다.
문제에서 players와 callings의 최댓값은 각각 50,000, 1,000,000이다. 내가 사용했던 indexOf는 두 번째 인자를 받지 않으면 순차적으로 탐색하는 함수였다. 즉, forEach와 indexOf를 사용한 연산은 이중 반복문이 되었다. 최대 50,000 * 1,000,000 = 50,000,000,000(500억)번 연산하므로 엄청난 시간이 걸릴 수밖에 없었다.
idx에 바로 접근하는 방법을 모색하다 hashmap 형식을 떠올렸다. 객체는 키만 알면 곧장 접근이 가능하고, 값으로 players의 idx를 넣어두면 확인도 쉽기 때문이다. 이름을 키로, 인덱스를 값으로 하는 answer 객체를 만들었다.
callings의 요소 하나가 v라면, 이전 인덱스는 answer[v]값의 -1이 되고, 현재 인덱스는 answer[v]값이 된다. players에 해당 인덱스로 접근한 값을 다시 answer의 키로 사용해 현재 인덱스와 이전 인덱스를 교환했다. players 배열의 요소 역시 위치를 바꿔주었다.
마지막으로 객체를 [key, value] 형태의 배열로 만들어주는 entries를 사용하고, value를 오름차순으로 정렬한 후, 다시 map으로 새 배열을 만들어 반환했다.
배운점
- 시간 복잡도에 걸릴 정도로 배열의 길이가 길다면,
hashmap형태로 접근해 인덱스를 얻는 편이 낫다. indexOf는 유용하지만, 두 번째 인자(fromIndex)가 없으면 순차 탐색(O(n))을 하니 배열의 길이가 짧을 때 사용해야 한다.
참고
