백준 10972 / 다음 순열

문제

풀이

설명

사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
2. j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i] 부터 순열을 뒤집는다.

순열 : 7 2 3 6 5 4 1

A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾아야 한다.

코드

import java.util.Scanner;

public class Num10972 {
	
	public static boolean next_permutation(int[] a) {
		int i = a.length-1;
		
		while (i > 0 && a[i-1] >= a[i]) {
			i -= 1;
		}
		if (i <= 0) {
			return false;
		}
		
		int j = a.length-1;
		while (a[j] <= a[i-1]) {
			j -= 1;
		}
		
		int temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        if (next_permutation(a)) {
            for (int i=0; i<n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
	}
}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/10972