/ BOJ

BOJ_10973_이전순열_JAVA

문제 : 이전순열

링크 : BOJ_10973_이전순열

접근 방식

순열을 구하는 방법 중에, Next Permutation 이라는 방법이 있다. 현재 수열보다 더 큰 바로 다음 순열을 구하는 방법이다.

이 문제는 이 방법을 반대로 수행하여 현재 수열보다 작은 바로 이전 순열을 구하면 되는 문제이다.

방법 자체는 간단했다. 순열을 읽어와서, Next Permutation의 코드를 반대로 수행시켜주면 된다.

소스 코드

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

public class BOJ_10973_이전순열 {

	static int N, arr[], input[];

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		arr = new int[N];

		input = new int[N];

		// 오름차순 배열
		for (int i = 0; i < N; i++) {
			arr[i] = i + 1;
			input[i] = Integer.parseInt(st.nextToken());
		}
		boolean check = false;
		for (int i = 0; i < N; i++) {
			if (arr[i] != input[i]) {
				check = true;
				break;
			}
		}

		if (!check) {
			System.out.println(-1);
			return;
		}

		nextPerm();
		for(int i=0;i<N;i++) {
			System.out.print(input[i]+" ");
		}

	}

	public static boolean nextPerm() {

		int i = N - 1;

		int[] answer = input.clone();

		while (i > 0 && input[i - 1] <= input[i]) {
			i--;
		}
		if (i == 0) {
			return false;
		}

		int j = N - 1;
		while (input[i - 1] <= input[j]) {
			j--;
		}

		int temp = input[i-1];
		input[i-1] = input[j];
		input[j] = temp;

		int k = N - 1;

		while (i < k) {
			temp = input[i];
			input[i] = input[k];
			input[k] = temp;
			i++;
			k--;
		}

		return true;

	}

}