[Java] 백준 10972 - 이론 및 구현해보기

next permutation이란?

보통 순열과 조합을 구현할 때에는 재귀 함수를 사용하여 구현한다.

하지만 재귀적인 함수의 호출은 구하고자 하는 범위가 넓어질 경우 사용하기 힘들다는 단점이 있다.

이런 단점을 해결할 수 있는 것이 next permutation이라는 알고리즘이다.

 

단순 일차원 탐색을 통해서 순열, 조합을 구할 수 있다는 장점이 있다.

반복문을 통해서 값을 구하기 때문에 원소의 개수가 N이라 할 때 O(N) 만큼의 시간 복잡도를 가진다.

값을 바꿔주는 swap 과정을 거쳐서 순열을 생성하기 때문에 자연스럽게 순열의 순서도 파악할 수 있다는 장점이 있다.

---

알고리즘 진행

1. 아래와 같은 배열이 주어졌을 때 배열의 맨 뒤에서부터 탐색을 시작하여 N[index] < N[index+1]인 가장 마지막 인덱스를 구한다.

 

위의 예시로 들면, 뒤에서부터 탐색을 시작하여 N[index] < N[index+1]을 만족하는 index를 pivotIndex라 한다.

여기서 pivotIndex 값은 2이다.

만약 pivotIndex가 음수가 나온다면, 뒤에 값이 앞의 값보다 큰 게 없다는 의미가 되므로, 마지막 순열임을 의미한다.

 

2. pivotIndex의 바로 뒤 인덱스부터, 맨 끝까지 탐색을 진행한다. 이 때, N[pivotIndex]의 값인 1보다 큰 값을 가지면서 가장 뒤에 있는 인덱스를 구한다. 이 인덱스를 j 라 하겠다.

위의 예시에서, 1보다 큰 값을 가지면서 가장 뒤에있는 인덱스는 맨 끝인 4이다. 따라서 j값은 4가 된다.

 

3. N[j] 가 N[pivotIndex] 보다 큰 값을 가진다는 것은 보장되어있는 상태이다. 따라서 N[j]와 N[pivotIndex]의 값을 교환해준다.

4. pivotIndex+1 부터, 맨 뒤까지 순서를 거꾸로 하는 reverse 작업을 진행해준다. 마지막 과정으로 나온 순열이 바로 그다음 순열이 된다.

---

문제 풀이

위 로직을 바탕으로, 구현은 해당 사이트 를 참고했다.

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

public class N10972 {
    // 다음 순열
    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[] givenArray = new int[N];

        int idx = 0;
        while(st.hasMoreTokens()) {
            givenArray[idx++] = Integer.parseInt(st.nextToken());
        }

        findNextPermutation(givenArray);
    }

    public static void findNextPermutation(int[] givenArray) {
        // 주어진 배열의 크기가 비어있거나, 원소가 1개인 경우 next_permutation은 불가능하다.
        if(givenArray.length <= 1) {
            System.out.println("-1");
            return;
        }

        // index + 1을 할 것이기 때문에, 마지막 인덱스인 givenArray.length - 1 을 넘지 않기 위해 -2 를 마지막 인덱스로 설정해준다.
        int pivotIndex = givenArray.length - 2;

        // 교체할 값인 pivotIndex를 찾지 못했을 경우, pivotIndex는 음수가 되며 while문을 나오게 된다.
        while(pivotIndex >= 0) {
            if(givenArray[pivotIndex] < givenArray[pivotIndex+1]) {
                break;
            }
            pivotIndex--;
        }

        // pivotIndex가 0보다 작을 경우, 다음 순열이 없는 마지막 순열이 된다.
        if(pivotIndex < 0) {
            System.out.println("-1");
            return;
        }

        int nextIndex = givenArray.length - 1;

        // 가장 마지막 원소부터, N[i] < N[i+1]을 만족하는 index 값보다 큰 인덱스인 nextIndex를 구한다.
        for(int i=nextIndex; i > pivotIndex; i--) {
            if(givenArray[i] > givenArray[pivotIndex]) {
                nextIndex = i;
                break;
            }
        }

        // nextIndex와 pivotIndex의 값을 교체한다.
        int tmp = givenArray[nextIndex];
        givenArray[nextIndex] = givenArray[pivotIndex];
        givenArray[pivotIndex] = tmp;

        // pivotIndex 오른쪽에 있는 값부터 마지막 인덱스까지 오름차순 정렬한다.
        int start = pivotIndex + 1;
        int end = givenArray.length - 1;

        while(start < end) {
            int swapTmp = givenArray[start];
            givenArray[start] = givenArray[end];
            givenArray[end] = swapTmp;

            start += 1;
            end -= 1;
        }

        for(int value : givenArray) {
            System.out.print(value + " ");
        }
    }
}