HackerRank Java New Year Chaos

문제풀기 : https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays&h_r=next-challenge&h_v=zen

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  from  at the front of the line to  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  and  bribes , the queue will look like this: .

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. 

minimumBribes has the following parameter(s):

• q: an array of integers 

Input Format

The first line contains an integer , the number of test cases. 

Each of the next  pairs of lines are as follows: 
- The first line contains an integer , the number of people in the queue 
- The second line has  space-separated integers describing the final state of the queue. 

Constraints

Subtasks

For  score 
For  score 

Output Format

Print an integer denoting the minimum number of bribes needed to get the queue into its final state. Print Too chaotic if the state is invalid, i.e. it requires a person to have bribed more than  people.

Sample Input

2
5
2 1 5 3 4
5
2 5 1 3 4

Sample Output

3
Too chaotic

Explanation

Test Case 1

The initial state:

After person  moves one position ahead by bribing person :

Now person  moves another position ahead by bribing person :

And person  moves one position ahead by bribing person :

So the final state is  after three bribing operations.

Test Case 2

No person can bribe more than two people, so its not possible to achieve the input state.

문제 요약 : 원더랜드 롤러코스터를 타기위해서 줄을 서있다.

줄을 서서 기다리는 사람은 일인당 2번 앞사람을 매수 해서 줄을 앞으로 갈 수 있다.

5명 일 경우

처음대기 순서는 1, 2, 3, 4, 5 로 되어있지만,

결론적으로 2, 1, 5, 3, 4로 줄이 되어있을 때,

원래의 줄에서 최소 몇번 매수가 일어나야지 현재의 줄로 가능한지 구하는 문제이다.

일인당 매수 횟수가 2번을 넘겼을 경우 "Too chaotic"을 출력하고,

2번을 넘기지 않았을 경우 최소 매수횟수를 출력한다.

접근 방법 : 

첫 번째로 생각한 방법이 원래의 위치에 있어 할 사람이 앞으로 이동했을 경우,

 인덱스의 차를 가지고 접근했다.

ex)

2, 1, 5, 3, 4 의 경우

1, 0, 4, 2, 3 이 원래의 위치 index이다.

0, 1, 2, 3, 4 를 각각의 index를 빼준다.

1-0, 0-1, 4-2, 2-3, 3-4 => 1, -1, 2, 1, -1

여기서 양수값이 2보다 클 경우 2번 넘게 매수를 했는경우라서 "Too chaotic"을 출력해 주었다.

그리고 양수값을 모두 더하면, 3이고

3이 최소 매수 횟수로 출력을 해주었지만,

이경우 소량의 테스트 케이스만 통과 했었다.

반례를 보았다.

반례 => 8명

1, 2, 5, 3, 7, 8, 6, 4

위의 logic으로 실행 했을 경우, 

0, 1, 4, 2, 6, 7, 5, 3

0, 1, 2, 3, 4, 5, 6, 7

0-0, 1-1, 4-2, 2-3, 6-4, 7-5, 5-6, 3-7 => 0, 0, 2, -1, 2, 2, -1, -4

로 합이 6이 나온다. 하지만 답은 7이다.

따라서 놓치는 부분이 있었다.

6번의 사람은 매수를 한 번 했었다. 하지만 7번 8번의 사람이 매수를 2번씩 진행 하면서

현재의 로직에서는 6번 사람은 매수를 한 번도 하지 않은 결과로 나와서 7이 아닌 6이 나왔다.

두 번째로 순수하게 내가 생각해낸 로직이 아니다. 아무리 생각해도 해법이 떠오르지 않아서 Discusstion 섹션에서 댓글들을 보았다. 아래처럼 설명하고 있었다.

Since the question only asks the number of bribes, there's no need to really do a sorting, nor element swapping, nor "bubbling up" an element. All you need to do is to count the number of people who overtake a person.

void calc(vector<int> q)
{
    int ans = 0;
    for (int i = q.size() - 1; i >= 0; i--) {
        if (q[i] - (i + 1) > 2) {
            cout << "Too chaotic" << endl;
            return;
        }
        for (int j = max(0, q[i] - 2); j < i; j++)
            if (q[j] > q[i]) ans++;
    }
    cout << ans << endl;
}

이 사람은 줄 맨 뒤에서 부터 접근하면서 매수를 먼저 2번 이상했는지 체크하고 2번을 넘지 않는다면, 중첩 포문으로 들어가서 매수를 했는지 체크하는 로직을 구현했다. 생각지도 못했는데, 나는 아직 멀었구나 생각했다.