문제

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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }

        int pos = n - 1;
        while(pos > 0 && data[pos - 1] > data[pos]){
            pos--;
        }

        int mPos = pos;
        if (pos > 0) {
            for (int i = n - 1; i >= pos; i--) {
                if (data[i] > data[pos - 1]) {
                    mPos = i;
                    break;
                }
            }
            int temp = data[mPos];
            data[mPos] = data[pos - 1];
            data[pos - 1] = temp;

            reverse(data, pos, n - 1);

            for (int i = 0; i < n; i++) {
                System.out.print(data[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println(-1);
        }
    }

    static void reverse(int[] data, int str, int end) {
        int[] temp = new int[end - str + 1];
        int j = 0;
        for (int i = temp.length - 1; i >= 0; i--) {
            temp[i] = data[str + j];
            j++;
        }

        for (int i = 0; i < temp.length; i++) {
            data[str + i] = temp[i];
        }
    }
}