백준 10972: 다음 순열(JAVA)

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

어떤 순열이 주어지면 사전순으로 다음에 오는 순열을 구하는 문제이다. 알고리즘 분류는 수학과 조합론이다.

 

1 2 3 4

1 2 4 3

1 3 2 4

...

 1) 배열의 끝부터 a[i]  > a[i-1] 인 구간을 찾는다.

 

 2) a[i-1]과 a[i...last]까지 중 가장 작은 값의 자리를 바꾼다.

    이때 a[i...last]는 내림차순으로 정렬되어있으므로 (-> 1전 과정을 찾기 전까지는 a[i] <= a[i-1]이므로) 뒤에서부터 탐색해 가장 먼저 발견되는 수랑 바꾸면 된다. 

 

 3) a[i]부터 오름차순으로 정렬한다. 

    내림차순으로 정렬되어 있으므로 역순으로 만들면 된다. 

 

 

import java.util.*;
public class Main {
	 public static void swap(int [] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
     public static boolean nextPermutation(int[] a) {
             // 인덱스 끝부터 a[i-1] < a[i]를 만족하는 첫 번째 수 찾기
            int i = a.length-1;
            while (i > 0 && a[i-1] >= a[i]) {
                i--;
            }
 
            // 마지막 순열인 경우 (= 위의 루프가 i가 0이 될 때 까지 돈 경우)
            if (i <= 0) {
                return false;
            }
            
           //뒤에서부터 i까지 a[i-1] < a[j]를 만족하는 첫 번째 수 찾기
            int j = a.length-1;
            while (a[j] <= a[i-1]) {
                j--;
            }
            
            //a[i-1]과 a[j] 자리 바꾸기
            swap(a, i-1, j);
 
            //i부터 a.length-1까지 순열 뒤집기
            j = a.length-1;
            while (i < j) {
                swap(a, i, j);
                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 (nextPermutation(a)) {
                for (int i=0; i<n; i++) {
                    System.out.print(a[i] + " ");
                }
            } 
            else {
                System.out.println("-1");
            }
        }
}