문제 링크
https://www.hackerrank.com/challenges/new-year-chaos/problem?h_r=profile
풀이
이번 문제는 두가지 방법을 고안해서 풀어보았지만, 결국 time limit exceed를 받아서 60%정도가 최선이었던 문제였다. 그래서 어떻게 풀었는지, 왜 안 됐는지를 생각해보았다.
실패코드 1
일단 문제를 대충 확인 해보니 기존 배열과 목표로 하는 배열의 값이 인덱스가 얼마나 차이가 나는지를 알면 금방 구할 수 있을 것 같았다. 왼쪽으로 이동한 경우 음수, 반대는 양수가 나올 텐데, 문제에서는 ‘앞으로’ 이동이 가능하다고 되어있었기 때문에 이런 인덱스 차이 중 음수인 부분만 체크하기로 했다.
이 중에서 -3 이상 벌어질 경우 제한 조건이었던 ‘최대 2칸만 이동가능’에 위반하므로 이 경우는 조건문으로 처리했다. 그 다음, 음수인 값들을 전부 누적시켜서 모든 앞으로 움직인 값들이 전부 몇 칸 움직였는지를 체크하여 답으로 반환했다.
틀린 이유: [1,2,5,3,7,8,6,4]
이 경우 정답은 5→2칸, 7,8→2칸, 마지막으로 6→1칸으로 총 7번 이동이 필요하다. 이 케이스에서 문제가 되는 부분은 바로 6이다.
마지막에 6은 한칸 앞으로 움집여서 4의 앞으로 이동했는데 전체적으로 따지면 6은 본래 위치에서 1칸 오른쪽에 위치해서 이 해법으로는 답에 누적이 되지 않는 것이다.
실패코드 2
이번에는 다른 관점에서 문제를 생각해보았다. 원래 순차적인 배열이었다면 자신의 왼쪽에는 오로지 자신보다 작은 숫자만 있을 것이다. 그런데 어떤 숫자가 앞으로 이동하게 되면 반대로 오른쪽으로 밀린 숫자 입장에서는 자신보다 큰 숫자가 1개 생기는 꼴이 된다.
이걸 이용해서 모든 배열을 돌면서 자신의 왼쪽에 자신보다 큰 숫자가 몇 개인지를 체크해서 누적시키면 답을 구할 수 있을 것 같았다. (이 경우는 실패 1번처럼 6의 경우를 누락시키지도 않는다.)
틀린 이유
문제 해법이 틀렸다기 보다는 시간의 부족으로 11케이스 중 6케이스 정답 처리가 되었다. 아무래도 n의 길이인 배열에서 모든 요소에 대해 자신의 앞을 검사하게 했으니 시간복잡도가 O(n^2)가 되어서 문제가 되는 듯 싶다.
그런데 이 케이스를 해결할 방법이 더 생각이 나지 않았다.
코드
- 실패 코드1
function minimumBribes(q) {
// Write your code here
const distance = q.map((x,idx) => (idx+1) - x);
if(distance.find(x => x <= -3))
{
console.log('Too chaotic');
return;
}
const result = q.reduce((acc, cur, index)=>{
return acc + q.filter((x,filterIdx)=>(filterIdx < index) && x > cur).length;
}, 0);
console.log(result);
}- 실패 코드2
function minimumBribes(q) {
// Write your code here
const distance = q.map((x,idx) => (idx+1) - x);
if(distance.find(x => x <= -3))
console.log('Too chaotic');
const result = distance.reduce((acc, cur)=>{
if(cur < 0)
return acc - cur;
return acc;
}, 0);
console.log(result);
}
```