10973 이전 순열

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	9461	5737	4738	63.030%

문제

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

5
5 4 3 2 1

예제 출력 2

5 4 3 1 2

코드

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

public class P_10973 {
    static int              n;
    static Integer[]        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).boxed().toArray(Integer[]::new);
        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, Collections.reverseOrder());
            for (int num : perm) bw.write(num + " ");
        }
    }
}

코드 설명

[P.10972 다음 순열]과 비슷한 방식이다.

다른 점은 비오름차순인 구간을 찾는다는 것과, 비오름차순인 구간 사이에서 값 교환이 일어난다는 것, 그리고 내림차순 정렬을 해야한다는 것이다.

비오름차순인 구간을 찾는 것은 부등호 방향만 바꿔주면 되는데 문제는 내림차순 정렬이었다.
Java에서 내림차순 정렬을 쓰기 위해서는 Arrays.sort함수의 인자로 Collections.reverseOrder()를 넘겨주어야 하는데 이 때 int 배열이 아닌 Integer배열이어야 한다는 것이다.

코테를 위한 입력 방식 중 Integer를 바로 받을 수 있는 방식을 아직 못 찾아서 int 배열로 받은 뒤 배열 하나를 모두 순회하면서 Integer로 변환시켜주었다. 이 경우 메모리 낭비가 있는 것이므로 추후에 Integer를 바로 받을 수 있는 방식을 알게 된다면 수정할 계획이다.

Integer로 입력 받기 위해서

Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().toArray(Integer[]::new);

를 쓴다