[10972번] 다음 순열 ( 조합인데 순열임, 내림차순 )

---

조합문제라고 생각하면 nCr= n-1Cr-1 + n-1Cr 이 떠올라서 이걸로 어떻게 풀지? 라고 생각을 무의식적으로 하게 되는 것 같다.
조합 공식을 쓰는 문제도 있고 아닌 문제도 있다.
그래서 조합 공식이 적용이 안되면 빨리 다른 방법을 떠올리는 게 좋다.

---

✅ 내림차순 법칙

오름차순인 숫자를 내림차순으로 만드는 문제이다.
가장 작은 사례를 만족한다고 생각하고 조합문제를 푼다.
오름차순으로 시작하니까 제일 오른쪽부터 내림차순을 만족한다고 가정하자.

1 2 3 4이면 4는 숫자 하나이므로 내림차순 만족.
3 4는 내림차순을 만족하지 않는다. -> 4와 3을 swap한다.
1 2 4 3이면 4 3은 내림차순 만족.
2 4 3이면 내림차순을 만족하지 않는다. -> 4 3중에서 2보다 큰 가장 작은 숫자와 swap한 한 후에 (3 4 2) 3이후를 오름차순 시킨다 (324)

7 2 3 6 5 4 1 같은 경우엔
7 2 3 / 6 5 4 1 -> 6 5 4 1이 내림차순이기 때문에
이것은 7 2 3으로 시작하는 순열중 마지막 내림차순 순열이다.
그러므로 7 2 3 다음으로 올 수 있는 오른쪽 에서 가장 큰 수
4와 swap하고 뒤집음으로써 오름차순으로 정렬하면 다음 첫 오름차순 순열이 나오게 된다. (7 2 4 1 3 5 6)

배열 인덱스로 구현하는 게 젤 어렵다ㅜㅠㅠㅜㅠㅜㅠㅜㅠㅜ제발 문제로 나오지마세요 🥺

---

✅ 코드

원본 배열을 건드린 코드이다.

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

public class Main {

	static int arr[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		arr = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		if (nextPermutation()) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
		} else {
			System.out.println(-1);
		}
	}

	private static boolean nextPermutation() {

		int i = arr.length - 1;

		while (i > 0 && arr[i - 1] > arr[i]) {
			i--; //1342면 i가 3일 때까지 --
		}

		if (i == 0) return false; //모두 내림차순이면 false


		int j = arr.length - 1; //맨오른쪽

		while (arr[j] < arr[i - 1]) { //맨 오른쪽부터 왼쪽으로 오면서 3보다 큰 숫자가 없으면 계속 왼쪽으로 이동한다.
			// 처음 접하는 3보다 큰 숫자가 오면 그게 내림차순 수열에서 가장 작은 수이다.
			j--; //
		}

		//2보다 큰 숫자가 j번째 -> swap 연산
		int temp = arr[i - 1];
		arr[i - 1] = arr[j]; //3을 4와 swap
		arr[j] = temp;

		//32를 오름차순 정렬
		int k = arr.length - 1;
		while (i < k) { // swap한 배열의 +1 번 인덱스 (i) 부터 끝까지 가면서
			temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
			i++; //이러면 for문이랑 똑같은 코드!
			k--;
		}
		return true;
	}

}

---