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

❔ 문제 설명

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,4,5,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 , 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.

⚠️ 제한사항

• $1 ≤ t ≤ 10$

• $1 ≤ n ≤ 10^5$

---

💡 풀이 (언어 : Java)

풀이 방법이 생각나지 않아 타인의 풀이를 공부했다. 버블 정렬을 이용해서 원래대로 순서대로 돌리는 알고리즘이었다. 하지만 시간복잡도에서 4개의 케이스가 탈락하면서 어떻게 시간복잡도를 줄일지 이것저것 많이 시도해보았다. 하지만 다 실패했고 이중 for문은 쓸 수 밖에 없는데을 어떻게 조금이라도 줄일까? 계속 고민하다가 이미 정렬이 완료되어도 뒤에서 계속 체킹하는 것을 줄여보기로 했다. 이를 위해서는 주어진 배열을 정렬한 또다른 배열을 준비하고 매 반복마다 체킹해서 같으면 함수를 종료하도록 했다. 이 알고리즘은 다행이 통과해서 정답 판정을 받았다. 이 과정에서 깊은 복사 clone()과 정렬 Arrays.sort()를 배웠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	private static void minimumBribes(int n, int[] intArr) {
		int count = 0;
		// 일단 처음부터 2번 이상 뇌물을 준 케이스가 있는지 부터 검사, 있으면 더이상 진행없이 종료
		for (int i = 0; i < n; i++) {
			if (intArr[i] > i + 3) {
				System.out.println("Too chaotic");
				return;
			}
		}
		// 정렬된 배열을 깊은 복사로 만들어서 비교 작업에 쓴다
		int[] copyArr = intArr.clone();
		Arrays.sort(copyArr);
		// 버블 정렬 시행, 서로 위치 바뀔때마다 카운트
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1 - i; j++) {
				if (intArr[j] > intArr[j + 1]) {
					int tmp = intArr[j + 1];
					intArr[j + 1] = intArr[j];
					intArr[j] = tmp;
					count += 1;
				}
			}
			// 버블 정렬 안쪽 for문에서 이미 정렬 완료되었는지 매번 체크해주어 불필요한 반복 줄임
			// 배열의 원소뿐만아니라 원소의 순서까지 같아야 true 반환함
			if (Arrays.equals(intArr, copyArr)) {
				break;
			}
		}
		System.out.println(count);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(br.readLine());
			// 정수 배열로 만들기
			int[] intArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			minimumBribes(n, intArr);
		}
	}
}