10972 다음 순열

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	20767	8592	6211	41.915%

문제

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을 출력한다.

예제 입력 1

4
1 2 3 4

예제 출력 1

1 2 4 3

예제 입력 2

5
5 4 3 2 1

예제 출력 2

-1

코드

import java.io.*;
import java.util.Arrays;

public class P_10972 {
    static int      n;
    static int[]    perm;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        perm = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        find_next_perm();

        bw.flush();
    }

    public static void find_next_perm() throws IOException {
        int idx = -1;

        for (int i = n - 2; i>= 0; i--) {
            if (perm[i] < perm[i + 1]) {
                idx = i;
                break;
            }
        }

        if (idx == -1) bw.write("-1");
        else {
            for (int j = n - 1; j > idx; j--) {
                if (perm[j] > perm[idx]) {
                    int temp = perm[j];
                    perm[j] = perm[idx];
                    perm[idx] = temp;
                    break;
                }
            }
            Arrays.sort(perm, idx + 1, n);
            for (int num : perm) bw.write(num + " ");
        }

    }
}

코드 설명

처음에는 백트래킹 방법으로 풀었는데 양쪽으로 이동해야하는 백트래킹 방식이라서 시간 초과가 발생했다.
그래서 규칙을 찾아서 바꿔주는 방식으로 코드를 재작성했다.

숫자에 층이 있다고 생각하자.
예를 들어서 1 2 4 3 같은 경우, 순열을 뒤에서부터 살펴보았을 때 4 3은 내림차순이지만 2 4 3은 비내림차순이므로 2와 4 사이에 층이 하나 있다.
이 층을 기점으로 숫자를 바꿔주면 되는데 마찬가지로 뒤에서부터 살펴본다.
층이 나뉜 기점인 2와 가장 뒷 숫자인 3을 비교를 해 보고 2 3은 비내림차순이므로 두 자리의 숫자를 바꾼다.
그러면 순열은 1 3 4 2가 된다.

이렇게 자리를 픽스해주고 나서는 층의 기점이었던 두번째 자리의 뒷부분을 오름차순으로 정렬해주면 된다.
그러면 순열은 1 3 2 4가 된다.

이런 식으로 다음 순열을 구해주었다.