제이

[Problem]

It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to n at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n=5 and person 5 bribes person 5, the queue will look like this: 1,2,3,5,4,6,7,8.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

[Function Description]

Complete the function minimumBribes in the editor below. It must print an integer representing the minimum number of bribes necessary, or Too chaotic if the line configuration is not possible.

요약하자면 정렬되지 않은 1부터 n까지의 수로 이루어진 배열이 주어지고, 이 배열을 오름차순으로 정렬할 때 최종적으로 자리바꿈 횟수를 구하는 문제이다. 또한, 만약 하나의 수가 3번 이상 자리바꿈이 이루어졌을 때 "Too chaotic"을 출력해야한다.

버블정렬을 이용하여 문제를 해결하려 했지만(1번), 일정 크기 이상의 배열이 주어졌을 때 시간 초과로 100% 통과를 하지 못했다. 배열 크기에 대한 처리를 어떻게 해야할지 생각이 나지 않아서 Discussion의 최고의 답변 으로 채택된 코드를 봤는데... 굳이 정렬을 실행 할 필요 없이 배열의 index와 해당 수의 차이만으로 문제를 해결한 것 같다. 

• 버블정렬 이용

function minimumBribes(q) {
    let numOfbribe = 0;
    let tmp;
    let chaotic = 0;
    let isChaotic = false;
    let continously = false;

    // Bubble sort
    // 연속으로 3번 바꾸면 Too chaotic 출력
    for (let i = 0; i < q.length - 1; i++) {
        for (let j = 0; j < q.length - i - 1; j++){
            if (q[j + 1] < q[j]) {
                tmp = q[j];
                q[j] = q[j + 1];
                q[j + 1] = tmp;

                numOfbribe++;   // 자리바꿈 한 횟수
                chaotic++;      // 한 가지 수가 몇번? => 3번이상되는지 체크하기 위함
                continously = true;
            } else {
                chaotic = 0;
                continously = false
            }
            if (chaotic === 3) { //한가지 수가 3번 교환되면 chaotic
                isChaotic = true;
                break;
            }
        }
    }

    if (isChaotic) console.log('Too chaotic');
    else console.log(numOfbribe);
}

• 인덱스와 숫자의 차이만을 이용

function minimumBribes(q) {
    //q의 인덱스i에 오는 수가 i+1과 차이가 3이상 나면 Too chaotic
    let ans = 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]) ans++;
        }
    }

    console.log(ans);
}

느낀점

• 문제에서 요구하는 사항을 잘 파악하고 불필요한 기능은 넣지 않는다.
• 배열의 notation만으로도 많은 것을 해결할 수 있다.