[HackerRank] New Year Chaos

Problem

---

It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.

 

Example

q = [1, 2, 3, 5, 4, 6, 7, 8]

If person 5 bribes person 4, the queue will look like this: 1, 2, 3, 5, 4, 6, 7, 8. Only 1 bribe is required. Print 1.

q = [4, 1, 2, 3]

Person 4 had to bribe 3 people to get to the current position. Print Too chaotic.

 

Function Description

Complete the function minimumBribes in the editor below.

minimumBribes has the following parameter(s):

• int q[n]: the positions of the people after all bribes

Returns

• No value is returned. Print the minimum number of bribes necessary or Too chaotic if someone has bribed more than 2 people.

Input Format

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

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

Constraints

• 1 ≤ t  ≤  10 
• 1 ≤ n ≤ 10^5

Subtasks

For 60% score 1 ≤ n ≤ 10³
For 100% score 1 ≤  n ≤  10^5 

Sample Input

STDIN       Function
-----       --------
2           t = 2
5           n = 5
2 1 5 3 4   q = [2, 1, 5, 3, 4]
5           n = 5
2 5 1 3 4   q = [2, 5, 1, 3, 4]

Sample Output

3
Too chaotic

Explanation

Test Case 1

The initial state:

After person 5 moves one position ahead by bribing person 4:

Now person 5 moves another position ahead by bribing person 3:

And person 2 moves one position ahead by bribing person 1:

So the final state is 2, 1, 5, 3, 4 after three bribing operations.

 

Test Case 2

No person can bribe more than two people, yet it appears person 5 has done so. It is not possible to achieve the input state.

 

---

새해 첫날에 사람들이 Wonderland 롤러코스터를 타기 위해 줄을 서 있습니다. 각 사람은 줄 서기 시작할 때의 위치를 나타내는 스티커를 1부터 nnn까지의 숫자로 가지고 있습니다. 각 사람은 바로 앞의 사람에게 최대 두 번까지 뇌물을 줄 수 있으며, 그 사람과 자리를 바꿀 수 있습니다. 다만, 사람들은 원래 스티커 번호를 계속 붙이고 있습니다.

주어진 줄 서기 상태로 변경되기 위해 필요한 최소 뇌물 수를 구하세요. 만약 어떤 사람이 두 번 이상의 뇌물을 준 경우, "Too chaotic"을 출력합니다.

 

예시

• q=[1,2,3,5,4,6,7,8]
  • 5번 사람이 4번 사람에게 뇌물을 주어 자리를 바꾸면, 줄은 [1, 2, 3, 5, 4, 6, 7, 8]이 됩니다. 필요한 뇌물 수는 1이며, 결과는 1을 출력합니다.
• q=[4,1,2,3]
  • 4번 사람이 3명에게 뇌물을 주어야 현재 위치에 도달할 수 있기 때문에, "Too chaotic"을 출력합니다.

 

함수 설명

 

함수를 완성하여 최소 뇌물 수를 출력하거나 "Too chaotic"을 출력하세요.

minimumBribes 함수는 다음 매개변수를 받습니다:

• int q[n]: 모든 뇌물 거래가 완료된 후 사람들의 최종 줄 서기 상태

출력 형식:

• 뇌물의 최소 개수나 "Too chaotic"을 출력합니다.

 

 

 

 

 

Solution

---

public static void minimumBribes(List<Integer> q) {
    int bribes = 0;

    for (int i = 0; i < q.size(); i++) {
        int originalPosition = q.get(i) - 1;

        // 현재 위치에서 두 칸 이상 이동한 경우, "Too chaotic" 출력
        if (originalPosition - i > 2) {
            System.out.println("Too chaotic");
            return;
        }

        // 원래 위치에서 최대 두 칸 앞까지만 탐색하여 뇌물 수 계산
        for (int j = Math.max(0, originalPosition - 1); j < i; j++) {
            if (q.get(j) > q.get(i)) {
                bribes++;
            }
        }
    }

    System.out.println(bribes);
}

 

 

• 변수 초기화: bribes 변수를 0으로 초기화하여 총 뇌물 수를 추적합니다.
• 위치 확인 및 "Too chaotic" 체크:
  • 각 사람의 원래 위치를 originalPosition 변수에 저장하고, 현재 위치인 iii와의 차이를 확인합니다.
  • 만약 현재 위치와 원래 위치의 차이가 2보다 크다면, 해당 사람이 세 명 이상에게 뇌물을 준 것으로 간주하고, "Too chaotic"을 출력합니다.
• 뇌물 수 계산:
  • 뇌물은 두 칸까지 가능하기 때문에, Math.max(0, originalPosition - 1)에서 i까지 반복하면서 현재 사람보다 큰 번호가 앞에 있는 경우 뇌물 수를 증가시킵니다.
    • Math.max(0, originalPosition - 1): 원래 위치에서 두 칸 앞부터 현재 위치(i)까지 확인합니다. originalPosition - 1은 두 칸 앞까지만 탐색하겠다는 의미입니다. 만약 인덱스가 음수가 되면 탐색 범위는 0부터 시작하여 배열의 경계를 벗어나지 않도록 합니다.
  • if (q.get(j) > q.get(i)) { ... }
    
    • 이 조건은 누가 누구에게 뇌물을 주었는지 확인하기 위한 것으로, 앞에 있는 사람이 현재 사람보다 큰 번호를 가지고 있다면, 앞사람이 뒤로 이동한 사람에게 뇌물을 준 것으로 간주하고 뇌물 횟수를 증가시킵니다.
• 출력:
  • 최종적으로 계산된 뇌물 수를 출력합니다.