백준 10972번 : 다음 순열

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

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

public class Main {
    StringBuilder sb = new StringBuilder();
    int n;
    int[] inputNum;
    boolean[] visit;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        inputNum = new int[n];
        visit = new boolean[n];
        for(int i=0; i<n; i++){
            inputNum[i] = Integer.parseInt(st.nextToken());
        }

        if(permutation(inputNum)){
            for(int a : inputNum){
                sb.append(a).append(" ");
            }
        }else{
            sb.append("-1");
        }
        System.out.println(sb);
    }

    public boolean permutation(int[] a){
        int i = a.length-1;
        while(i>0 && a[i-1]>=a[i]){
            i--;
        }

        if(i<=0) return false;

        int j = a.length-1;
        while(a[i-1]>=a[j]){
            j--;
        }

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

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


    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

다음 순열을 찾는 네 가지 순서가 존재한다.

 

첫 번째.

주어진 순열 마지막에서부터 내림차순이 끝나는 곳을 찾는다.

ex) 1 3 4 2 // a[i-1] = 3 , a[i] = 4

 

두 번째.

주어진 순열 마지막에서부터 j>=i, a[j] > a[i-1]를 만족하는가장 큰 j를 찾는다.

ex) 1 3 4 2 // a[i-1] = 3, a[j] = 4

 

세 번째.

a[i-1]과 a[j]를 스왑한다.

ex) 1 3 4 2 -> 1 4 3 2

 

네 번째.

a[i]부터 순열 마지막까지 스왑한다.

ex) 1 4 3 2 -> 1 4 2 3

 

1 3 4 2 에 다음 순열은 1 4 2 3 이다.