21.06.09 - [BOJ] 10972. 다음 순열

[suhyunsim]

문제

• 10972

핵심 아이디어

• N가지를 다 해봐야 하는데 순서가 중요한 경우
• 첫 순열 구하기 -> 다음 순열 구하기 ... -> 마지막 순열 구하기
  • 첫: 오름차순, 비내림차순 정렬
  • 막: 내림차순, 비오름차순 정렬
  • 다음:
    • 1. A[i -1] < A[i]를 만족하는 가장 큰 i를 찾는다. O(N)
    • 2. j >= i이면서 A[j] > A[i - 1]를 만족하는 가장 큰 j 찾기 O(N)
    • 3. A[i - 1]과 A[j]를 swap O(1)
    • 4. A[i]부터 순열 뒤집기 O(N)
         => O(N)
• 모든 순열: N! * N -> O(N * N!)

어려운 점, 실수

• 처음 보는 유형의 문제

풀이

package main.java.com.poogle.BOJ.Q10972;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        if (nextPermutation(a)) {
            for (int i = 0; i < n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }

    private static boolean nextPermutation(int[] a) { //다음 순열 있는지 판단
        int i = a.length - 1;
        //i찾기
        while (i > 0 && a[i - 1] >= a[i]) {
            i -= 1;
        }
        if (i <= 0) {
            return false;
        }

        //j찾기
        int j = a.length - 1;
        while (a[j] <= a[i - 1]) {
            j -= 1;
        }

        //swap
        int tmp = a[i - 1];
        a[i - 1] = a[j];
        a[j] = tmp;

        //a[i]부터 순열 뒤집기
        j = a.length - 1;
        while (i < j) {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i += 1;
            j -= 1;
        }
        return true;
    }
}