[Java]백준 10972번 :: 다음 순열

백준 온라인 저지 10972번 - 다음 순열

Java 알고리즘 문제풀이

풀이

완전탐색(BP)에 속하는 순열문제이다.

푸는 방법은 아래와 같다.

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]부터 순열을 뒤집는다.

ex) 7 2 3 6 5 4 1

1. 오른쪽부터 왼쪽이 작은 수를 찾는다. 3 < 6, 6선택 i = 3

2. 다시 오른쪽부터 확인해서 3보다 첫번째로 큰 숫자를 찾는다. -> 4

3. 3과 4를 자리를 바꾼다 -> 7 2 4 6 5 3 1

4. 바꾼 숫자의 오른쪽 전부를 뒤집는다. -> 7 2 4 1 3 5 6

import java.util.Scanner;

public class Beak10972 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] arr = new int[num];

        for (int i = 0; i < num; i++) {
            arr[i] = sc.nextInt();
        }

        nextPermutation(arr);

        sc.close();
    }

    private static void nextPermutation(int[] arr) {
        int n = arr.length;
        boolean b = true;
        Loop1: for (int i = n - 1; i > 0; i--) {
            if (arr[i - 1] < arr[i]) {
                for (int j = n - 1; j >= i; j--) {
                    if (arr[j] > arr[i - 1]) {
                        int temp = arr[j];
                        arr[j] = arr[i - 1];
                        arr[i - 1] = temp;
                        int k = n - 1;
                        while (i < k) {
                            int temp2 = arr[i];
                            arr[i] = arr[k];
                            arr[k] = temp2;
                            i++;
                            k--;
                        }
                        b = false;
                        break Loop1;
                    }
                }
            }
        }
        if (b) {
            System.out.println(-1);
        } else {
            showArray(arr);
        }
    }

    private static void showArray(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
    }
}