[Java]백준 10973번 :: 이전 순열

백준 온라인 저지 10973번 - 이전 순열

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. 오른쪽부터 왼쪽의 수가 큰 수를 찾는다. 4 > 1, i = 6

2. 다시 오른쪽부터 확인해서 4보다 첫 번째로 작은 수를 찾는다. -> 1

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

4. 바꾼 숫자의 오른쪽 전부를 뒤집는다.

import java.util.Scanner;

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

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

        previousPermutation(arr);

        sc.close();
    }

    private static void previousPermutation(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[i - 1];
                        arr[i - 1] = arr[j];
                        arr[j] = 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.print(arr[i] + " ");
    }
}