[Java] 다음 순열 Next Permutation

정의

단순히 현재 순열보다 다음에 올 큰 숫자를 찾는 것이다.
순열, 조합을 생성 할 때 재귀를 사용하지 않고 각 인덱스 값을 비교하는게 중점이다.
1,2,3으로 조합을 떠올려본다면 123->132->213->312->321 순서일 것이다.
132 다음에 올 수는 몇일까? 213이다 이것을 찾는 것이다.

구현

주어진 배열을 제일 작은 순서부터 제일 큰 순서로 오름차순 정렬을 한 후에 다음 큰 순열을 찾는 과정을 반복해야 한다.

1. 오른쪽에서 왼쪽으로 가면서 현재순서(i)와 오른쪽(i+1)를 찾고 i<i+1인 경우 i를 피벗 포인트로 둔다.
2. 피벗 포인트보다 오른쪽에 위치한 요소 중 피벗 포인트 값보다 크지만 그 중 가장 작은 값을 찾는다.
3. 피벗 포인트와 찾은 값의 위치를 바꾼다.

1. i와 i+1 포인트를 찾는다.

2. 피봇 포인트를 찾는다.

3. 피봇 포인트보다 크지만 그 중 가장 작은 값을 찾는다.

4. 위치를 바꾼다.

5. 반복하여 오름차순을 제작한다.

코드

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));
	}
}