[백준 10972 : JAVA] 다음 순열

문제

---

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

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

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

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

 

 

입력

---

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

 

 

출력

---

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

 

 

 

풀이

---

해당 문제는 이름 그대로 다음에 오는 순열을 찾을 수 있는지를 묻는 문제입니다.

 

다음과 같은 순열이 있다고 가정해보겠습니다.

P = [4, 6, 5, 7, 3, 2, 1]

 

위 순열 다음에 오는 순열은 무엇일까요? 바꿔 말해, 위 순열 4657321 다음으로 큰 수는 무엇일까요?

465 7321    <---- 7321만 봤을 때, 해당 수는 해당 수 조합에서의 가장 큰 수입니다. (내림차순 나열)

즉, 7321까지는 내림차순으로 그 다음 수가 없기 때문에 처음으로 내림차순이 꺾이는 지점인 5를 swap 해야합니다.

 

5와 그 뒤의 7321 중 하나를 swap해야하는데 어떤 수가 좋을까요?

바로 다음으로 큰 수여야하니까 5보다 큰 최소값일 것입니다. 즉, 5와 7을 swap해야 합니다.

 

467 5321 로 바꼈습니다. 다음으로 내림차순으로 되어있는 5321을 오름차순인 1235로 바꾸면 다음 순열이 완성됩니다 !

 

 

 

코드

---

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

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

    private static boolean nextPermutation() {
        int i = nums.length - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) { i--; }
        if (i <= 0) return false;

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

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

    private static void swap(int idx1, int idx2) {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}