[JAVA] 백준 10972번: 다음 순열 ( 초급 2-20 ) - hard

문제

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

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

• 첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

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

 

문제 풀이

예시 )

7 2 3 6 5 4 1

 

현재 순열 파악

7,236,541은 723으로 시작하는 마지막 순열이다.

마지막 순열은 내림차순으로 확인할 수 있다. ( 6 5 4 1 )

 

분기점 확인 

7 2 3 < 6 > 5 > 4 > 1

3과 6이 분기점이라는 것을 알 수 있다.

 

다음 순열 탐색

6, 5, 4, 1 중에서 3보다 크면서 최소인 수를 찾아야 한다. (4)

다음 순열은 724로 시작하는 첫 순열이다.

 

3과 4를 변경해주고, 내림차순이던 수를 오름차순으로 변경해준다.

1) 3과 4를 변경

7,236,541 -> 7,246,531

 

2) 내림차순 -> 오름차순

6531 -> 1356

7,246,531 -> 7,241,356

 

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

public class baekjoon10972_3 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] info = new int[num];

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

        // 12345
        int endIndex = num - 1;

        if (num == 1) {
            System.out.println(-1);
            System.exit(0);
        }

        while (endIndex != 0 && info[endIndex - 1] > info[endIndex]) {
            endIndex--;
        }

        if (endIndex == 0) {
            System.out.println(-1);
            System.exit(0);
        }
        int temp = info[endIndex];
        int tempIndex = endIndex;
        for (int i = endIndex + 1; i < num; i++) {
            if (info[i] > info[endIndex - 1] && info[i] < temp) {
                tempIndex = i;
                temp = info[i];
            }
        }

        info[tempIndex] = info[endIndex - 1];
        info[endIndex - 1] = temp;

        for (int i = 0; i < endIndex; i++) {
            System.out.print(info[i] + " ");
        }

        for (int i = num - 1; i >= endIndex; i--) {
            System.out.print(info[i] + " ");
        }
    }
}