📝 문제

📎 백준 10972 다음 순열

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

// 다음 순열 //
// 조합론

public class Baek_10972 {

    static int N;
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        A = new int[N];
        StringTokenizer st = new StringTokenizer(bf.readLine());

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

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

    }

    // 정렬 가능 여부 리턴
    public static boolean isCheckNum() {
        int i = A.length-1;
        while(i>0 && A[i]<A[i-1]) {
            i--;
        }
        if(i<=0) {
            return false;
        }

        int j = A.length-1;
        while(A[j]<A[i-1]) {
            j--;
        }
        swap(i-1,j);   

        j = A.length-1;
        while(i<j) {
            swap(i,j);
            i++;
            j--;
        }
        return true;
    }

    // 숫자 swap 함수
    public static void swap(int i,int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

✅ 문제 설명

• 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성한다.

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다.
만약, 사전순으로 마지막에 오는 순열인 경우에는 "-1" 을 출력한다.

✅ 문제 접근

• 예제 입력에 있는 순열 중에서 먼저 1 2 3 4 가 입력되었을 경우를 생각해보자.
  1 2 3 4 다음에 올 수 있는 수는 1 2 4 3 이다. 이 경우를 코드로 나타내면 다음과 같다.

(1)
int i = A.length-1;
        while(i>0 && A[i]<A[i-1]) {
            i--;
        }

(1) i 구하기

먼저 인덱스 i 를 "배열의길이-1" 로 잡는다. 이 경우 i= 3이 되겠다. i가 0보다 크고 이전 인덱스 보다 작은지 확인한다.
작다면 1 2 | 4 3 에서 4 3 처럼 더 가능 한 숫자가 없으므로 더 확인할 필요가 없기 때문이다.

 (2)
 int j = A.length-1;
        while(A[j]<A[i-1]) {
            j--;
        }

(2) j 구하기

다음으로 j 의 인덱스 역시 "배열의길이-1" 로 잡는다.
그리고 나서 j의 인덱스가 [i-1] 보다 작은지 확인해야 한다.

그 예시를 보자
예를 들어 1 2 4 3 이라는 순열이 있을 때,
다음 올 순열은 1 3 2 4 가 되어야 한다. 그 과정은 다음과 같다.
먼저 (1) 과정에 의해 i=2 가 된다. ( A[2]=4,A[1]=2 )
그리고 A[j]<A[i-1] 인지 확인한다. 즉 A[j]=A[3]=3 이 A[i-1]=A[1]=2 인지 확인한다. 만족하지 않으므로 둘의 위치를 바꾸어 준다.

(3)
j = A.length-1;
        while(i<j) {
            swap(i,j);
            i++;
            j--;
        }

(3) swap

swap 이 진행되었어도 (2) 과정을 통해 1 3 4 2 라는 순열이 나오게 된다. 이는 우리가 다음에 원하는 수인 1 3 2 4 와 다르다.
때문에 한번더 while 문을 통해 i,j 를 swap 해주는 과정이 필요하다.