[백준 *Java] - 다음 순열 (10972)

 

다음 순열

10972번: 다음 순열

👇  문제보기 

문제

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

---

👇 접근방식 [내생각 정리]

문제를 이해하기 위해서 처음엔 테스트케이스를 보면서 계속 문제를 읽었습니다...

그래서 처음 접근했던 방식은 방문처리를 먼저 생각하여 boolean을 이용하여 입력 받은 수열의 다음 수열을 가져오려고 했습니다. 

그런데, 만약 순열이 마지막일 경우 -1을 출력해야하는 부분을 해결해야하는데, 이 부분에선 코드구현을 한다면, 지저분하게 되고, 예외 테스트케이스에 걸릴 거 같아서 순열에 대해서 다시 생각하다가 생각이 나질 않아 다른 방법을 찾아보니,

swap 방법이 있다는 걸 알았습니다. 수동적으로 값을 교환해줘서 문제를 해결해 나갈 수 있다고 생각했습니다.

그리고,

순열 문제를 푸는 방식이 3가지가 있다는 걸 알았습니다 (저는...방문처리만 알고 있었네요....)

• iterative

> https://commons.apache.org/proper/commons-collections/jacoco/org.apache.commons.collections4.iterators/PermutationIterator.java.html

• 스왑
• 방문처리

스왑방식을 이용해서, 수동적으로 값을 교환하는 작업을 해주면서 문제를 구현하겠습니다.

---

 

다음 순열 문제를 풀 때, 

우리가 흔히 알고 있는 순열이 어떻게 변화하게 되는 지는 어느정도 알고 있으니,

그 규칙을 재귀가 아닌 수동으로 값을 swap을 해주기 위해서 재귀변화되는 과정의 규칙을 찾아야합니다.

 

1.

순열을보면, 뒤에서부터 swap되는 것처럼 값 이동이 이루어집니다.

고로, 순차적으로 값을 비교하기보단, 역순차로 생각을해야합니다.

 

2.

두 idx의 값을 비교를하면서, 증가하냐 증가하지 않느냐를 구분 해주어야합니다.

ex) N이 3일 때,
인덱스 0과 1를 확인해볼게요. 
증가되는 예,
1, 3, 2 -> 증가 1->3

3.

증가 되는 두 인덱스 번호 기준으로 절반으로 나누어, leftArea / rightArea 라하고 이 Area에서 가장 오른쪽 값들을 비교하여 rightArea 비교대상 값이 클 경우 swap

위의 값을 가지고 이어 설명합니다.
1 은 leftArea
3, 2는 rightArea
leftArea 의 제일 오른쪽과
rightArea 의 제일 오른쪽과 비교를 하여, rightArea 비교대상 값이 클 경우 swap
1, 3, 2
에서 1과 2를 비교하여 swap
2 3 1

4.

마지막 작업은 원래 132 다음순열이 231이 아닌 213 입니다. 그러니 rightArea 부분을 정렬해주어야 합니다.

 

 

위의 규칙을 가지고 구현을 하면 아래의 성공한 코드가 나옵니다.

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

public class Main {
    static int N;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    static void nextPermutation() {
        int idx = 0;
        int lastLen = N - 1; // 수열 인덱스 값 세팅

        // 순열은 뒤에서부터 작업이 시작됩니다.
        for (int i = lastLen; i > 0; i--) {
            if (arr[i - 1] < arr[i]) { // 현재 인덱스에서 그 전 인덱스를 비교해줍니다.
                idx = i; // 증가하는 부분 찾기
                break;
            }
        }

        if (idx == 0) {
            System.out.println(-1);
            return;
        }

        for (int i = lastLen; i >= idx; i--) {
            if (arr[idx - 1] < arr[i]) {
                swap(idx-1, i);

                // 부분정렬
                Arrays.sort(arr, idx, N);

                for (int s : arr) {
                    sb.append(s).append(" ");
                }

                System.out.println(sb);
                break;
            }
        }
    }

    static void swap(int v1, int v2) {
        int temp = arr[v1];
        arr[v1] = arr[v2];
        arr[v2] = temp;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

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

        nextPermutation();
    }
}