[백준] 10972번 다음 순열

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

10972번: 다음 순열

 

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

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
   
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }

        if(nextPermutation(arr)) {
            for(int val : arr) {
            	sb.append(val).append(" ");
            }
        } else {
        	sb.append("-1");
        }

        System.out.println(sb);
    }

    public static boolean nextPermutation(int[] arr) {

        int i = arr.length - 1;

        // arr[i-1] < arr[i] 를 만족하는 가장 큰 i
        while(i > 0 && arr[i-1] >= arr[i]) {
        	i--;
        }

        // i의 위치가 0이면 내림차순(마지막 순열)
        if(i<=0) {
        	return false;
        }

        int j = arr.length - 1;

        // j >=i 이면서 arr[j] > arr[i-1] 를 만족하는 가장 큰 i
        while( arr[i-1] >= arr[j]) {
        	j--;
        }

        // arr[i-1] 과 arr[j] 를 swap
        int temp = arr[j];
        arr[j] = arr[i-1];
        arr[i-1] = temp;

        j = arr.length - 1;

        // arr[j] 부터 순열 뒤집기
        while(i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }

        return true;
    }

}