[백준] 10972 - 다음 순열 [JAVA]

 

 

코드

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

public class Main {
    static int N;
    static int[] arr;

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

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        if (hasNextPerm()) {
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + " ");
            }
        } else System.out.print(-1);

    }

    static boolean hasNextPerm() {
        
        // 1. 순열 뒤에서부터 찾으면서 오름차순이 되는 지점 찾기
        int i = arr.length - 1;

        while (0 < i && arr[i - 1] >= arr[i]) {
            i--;
        }

        // 이미 내림차순으로 모두 정렬되어 있는 경우
        if (i == 0) return false;

        int j = arr.length - 1;

        while (arr[i-1] > arr[j]) {
            j--;
        }

        // 3. i와 j 값 교환
        swap(i - 1, j);

        // 4. i-1 부터 있는 순열이 모두 내림차순이니 이를 오름차순으로 뒤집는다
        j = arr.length - 1;

        // 5. 기존 오른쪽에 내림차순으로 되어있던 순열 ->  왼쪽에서 부터의 오름차순으로 만듦
        while (i < j) {
            swap(i, j);
            i ++; j --;
        }
        return true;
    }

    static void swap(int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

}