[Java]다음 순열(Next Permutation)

*다음 순열(Next Permutation).

-> 다음 순열이란, 말 그대로 해당 숫자의 다음에 올 순열의 수를 의미한다.

Ex) {1, 2, 3}에서 3개를 선택하는 경우 순열은 123, 132, 213, 231, 312, 321이 있다. 그렇다면 123 다음에 올 순열은 무엇일까? 132이다. 즉, 123의 다음 순열은 132임을 알 수 있다.

 

*다음 순열 구하기

-> 다음 순열을 구하는 로직은 우리가 무의식적으로 다음 순열을 구하는 로직을 천천히 곱씹으며 구체화시켜보면 가능하다. 우리는 이미 다음 순열을 구하는 방법을 알고 있다!(다만 막상 논리적 순서로 나타내보려 하면 헷갈리고 어려울 뿐이다...)

-> 규칙성을 찾기 위해서는, 작은 경우부터 침착하게 내가 어떻게 구하고 있는지 분석해보면 된다. 예를 들어, 집합 {1, 2, 3}에서 3개를 선택하는 순열은 다음과 같은 순서로 구한다.

우리는 이미 자연스럽게 다음 순열을 구할 줄 안다.

 

-> 우선 123의 다음 순열인 132를 구하는 과정을 생각해보자.

 우선 우리는 해당 수의 뒷 부분 부터 탐색하면서, 크기가 증가하는 부분을 찾는다(뒤에서 부터 찾으면, 2에서 3으로 증가하는 부분을 먼저 찾을 수 있다).

 이렇게 증가하는 부분을 찾았다면, 그 부분을 기준으로 좌/우 지점을 구분 한다.

 구분된 지점에 대하여, 좌측 지점의 가장 끝 숫자에 대하여 우측 지점에서 큰 수를 찾는다. 이때, 큰 수를 찾는 순서는 우측 지점의 제일 마지막 부분부터 시작한다.

 그렇게 찾은 숫자를 서로 Swap 해준다. 다음 순열을 처음 접하는 사람이라면, 우리가 이렇게 복잡한 과정을 당연히 하고 있었다는 사실에 신기함을 느낄 것이다. 하지만 여기서 끝난 것이 아니다. 한 가지 과정이 더 남아있는데, 그것은 다음 예시를 참고하자.

 

-> 다음으로, 132의 다음 순열인 213을 구하는 과정을 살펴보자.

 마찬가지로, 해당 수의 뒷 부분부터 탐색하면서 증가하는 부분을 찾는다.

 그 부분을 찾았다면, 그 지점을 기준으로 좌/우 지점을 구분한다.

 구분된 지점 좌측의 가장 우측 숫자에 대하여 우측 지점의 우측 끝 부분 부터 탐색하면서, 더 큰 수를 찾는다.

 그 숫자를 찾았다면, 각 숫자를 서로 Swap해준다. 하지만, 132의 다음 순열은 213인데 231이 나온 것을 확인할 수 있다. 즉, 아직 한 가지 로직이 더 남아 있음을 알 수 있다.

 

 마지막으로, 나눠진 지점의 우측 부분의 모든 수를 '오름차순' 정렬 해준다. 여기까지가 우리가 다음 순열을 구할 때 무의식적으로 하던 행위이다. 이렇게, 규칙성을 찾는 문제는 작은 문제부터 시작하여 자신의 로직이 맞는지 천천히 검증한다면 다음 순열 뿐 만 아니라 다른 문제도 비교적 쉽게 규칙성을 찾을 수 있다.

 

-> 이제부터는 단순히 '구현'의 문제이다. 이 모든 과정을 코드로 구현하기만 하면 된다. 아래 예시는 입력된 수의 다음 순열을 구하는 코드이다.

package cases;

import java.util.Arrays;
import java.util.Scanner;

public class NextPermutation {
	static int[] input;
	static int N;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 입력받은 수를 배열에 저장.
		String line = sc.nextLine();
		N = line.length();
		input = new int[N];

		for (int i = 0; i < line.length(); i++) {
			input[i] = line.charAt(i) - '0';
		}

		// 다음 순열.
		nextPermutation();
		sc.close();
	}

	private static void nextPermutation() {
		// 주어진 순열의 뒤부터 탐색하며, 증가하는 부분을 찾는다.
		int idx = N - 1;
		while (idx > 0 && input[idx - 1] > input[idx]) {
			idx--;
		}

		// 만일, 증가하는 부분이 존재하지 않는다면 다음 순열은 존재하지 않는 것이다.
		if (idx == 0) {
			System.out.println("다음 순열이 존재하지 않습니다. 마지막 순열 입니다.");
			return;
		}

		// 해당 인덱스를 기준으로, 좌/우 지점으로 나눈다.
		// 좌측의 제일 오른쪽 숫자에 대하여, 우측의 제일 오른쪽 지점부터 탐색하며 큰 수를 찾는다.
		int big_idx = N - 1;
		while (big_idx > idx && input[idx - 1] > input[big_idx]) {
			big_idx--;
		}

		// 해당 숫자를 찾았다면 각 숫자를 서로 Swap한다.
		int temp = input[idx - 1];
		input[idx - 1] = input[big_idx];
		input[big_idx] = temp;

		// 우측 지점을 정렬한다.
		Arrays.sort(input, idx, N);
		
		// 결과 출력
		System.out.println(Arrays.toString(input));
	}
}

※ for문으로 구현해도 된다.

package cases;

import java.util.Arrays;
import java.util.Scanner;

public class NextPermutation {
	static int[] input;
	static int N;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 입력받은 수를 배열에 저장.
		String line = sc.nextLine();
		N = line.length();
		input = new int[N];

		for (int i = 0; i < line.length(); i++) {
			input[i] = line.charAt(i) - '0';
		}

		// 다음 순열.
		nextPermutation();
		sc.close();
	}

	private static void nextPermutation() {
		// 주어진 순열의 뒤부터 탐색하며, 증가하는 부분을 찾는다.
		int idx = N - 1;
		for (int i = N - 1; i > 0; i--) {
			if (input[i - 1] < input[i]) {
				idx = i;
				break;
			}
		}

		// 만일, 증가하는 부분이 존재하지 않으면 다음 순열은 존재하지 않는 것이다.
		if (idx == 0) {
			System.out.println("다음 순열이 존재하지 않습니다. 마지막 순열 입니다.");
			return;
		}

		// 해당 인덱스를 기준으로, 좌/우지점을 나눈다.
		// 좌측의 제일 오른쪽 숫자에 대하여, 우측의 제일 오른쪽 지점부터 탐색하며 큰 수를 찾는다.
		// 해당 숫자를 찾았다면 각 숫자를 서로 Swap한다.
		for (int i = N - 1; i >= idx; i--) {
			if (input[idx - 1] < input[i]) {
				int temp = input[idx - 1];
				input[idx - 1] = input[i];
				input[i] = temp;
				break;
			}
		}
		
		// 우측 지점을 정렬한다.
		Arrays.sort(input, idx, N);
		
		// 결과 출력
		System.out.println(Arrays.toString(input));
	}
}