버블정렬? 뇌물의 횟수를 구하라! (feat. 새치기)

문제

1. 놀이기구를 타기 위해서 줄을 기다리고 있다.
2. 줄에서 대기하고 있는 어느 누구라도 뇌물을 줘서 앞으로 이동 할 수 있다.
3. 뇌물을 줄 수 있는 횟수는 최대 2회
4. 완성된 줄을 보고 뇌물이 총 몇 번 왔다 갔다 했는지 알아내라!

요구 사항

주어진 minimumBribes 함수를 완성 시켜라.

첫번째 인자는 배열(대기줄)
결과값은 뇌물의 총 횟수 또는 특정 인물의 뇌물 횟수가 2를 넘으면 'Too chaotic'을 return

입력 형식

첫번째 줄에는 테스트 케이스 개수
다음 줄 쌍은 다음과 같다.

• 첫 줄은 대기열에 있는 사람의 수
• 두번째 줄은 대기열의 상태

제한 사항

테스트 케이스 개수 1 <= t <= 10, 대기열의 사람 수 1 <= n <= 10의5승

예제

입력:
2
5
2 1 5 3 4
5
2 5 1 3 4

결과:
3
Too chaotic

풀이 과정

문제를 다 읽고 먼저 든 생각은 '버블정렬' 하면 끝나겠군.

이중 for문을 사용하여 원소가 이동 할 때마다 카운트 하는 방식으로 구현

깔끔!

하지만 결과는 Time out

버블 정렬이 O(n^2)인건 알고 있지... 그럼 최소 O(nlogn)으로 만들어야 한다는건데...허허

그때부터 고뇌의 시간을 가짐. 실질적으로 정렬이 필요 없다는 얘기. 횟수만 계산하면 된다....

맨 오른쪽에 있는 녀석은 뇌물을 다 받아 먹은놈

이 문장 하나로 알고리즘을 다시 재구성 하기 시작했다.

1. 현재 내 위치보다 앞에 있는 놈들은 나한테 뇌물을 준 놈이다.
2. 그 중에서 나보다 큰 수를 찾으면 된다.

여기서 문제 나보다 큰 수는 어디에 위치하고 있을까?

나보다 큰 수는 어디까지 갈 수 있는가? 이게 요점이다.

그건 모르겠고! 0부터 시작할래! 하면 아무 의미가 없다.

천천히 생각해보자.

예제 [2 1 4 5 3]

내가 만약 3이라면 나보다 앞에 갈 수 있는 놈은 2가 한계다. (원래 위치 기준 [1 2 3 4 5])

바로 내 뒤에 있는 4가놈이 3과 2한테 2번 뇌물을 주면 끝. 가고 싶어도 못간다.

위에 말을 알고리즘으로 표현하면,

시작점: MAX(0, 3 - 2) => 고로 시작점은 1이 된다. (위에서 2의 인덱스가 1이다.)
종료점: 현재 인덱스

for i = max(0, 3-2); i < 4; ++i

위에서 얻은 결론으로 알고리즘을 실제로 구현해보자.

function minimumBribes(q) {
    let totalCount = 0;
    for(let i = q.length-1; i >= 0; --i) {
        if(q[i] - (i+1) > 2) {
            console.log('Too chaotic')
            return;
        }

        for(let j = Math.max(0, q[i]-2); j < i; j++) {
            if(q[j] > q[i]) {
                totalCount += 1;
            }
        }
    }

    console.log(totalCount)
}