Next Permutation ? 

다음 순열이란, 말 그래도 해당 숫자의 다음에 올 순열의 수를 의미한다. 123 -> 132, 132 -> 213, 213 -> 231 ... 와 같다. 그렇다면 우리는 123의 다음 순열인 132를 구하는 과정을 살펴보겠다.

 

1. 해당 수의 맨 오른쪽부터 왼쪽으로 차례대로 $ i $ > $  i -1 $  이고, $ A_{i} $ > $ A_{i-1} $인 수를 찾는다.$ ( $$ i $는 인덱스 번호, $ A_{i} $는 해당 자리의 값$ ) $ 

 

2. 두 수 분리하기. 찾은 두 수를 막대를 하나 긋고, 임의로 왼쪽, 오른쪽으로 분리시킨다.

 

3. 왼쪽 공간의 가장 오른쪽 숫자에 대하여 오른쪽 공간의 우측 끝 부분 부터 왼쪽으로 탐색하면서, 더 큰 수를 찾는다. 

 

4. 왼쪽 공간의 가장 오른쪽 숫자와 오른쪽 공간에서 찾은 더 큰 수의 자리를 바꿔준다. 1 2 3 -> 1 3 2

 

5. 기존에 2와 3을 기준으로 공간을 나눴었다. 그리고 3과 2의 자리가 바뀌었다. 나눠진 지점(2)의 우측 부분의 모든 수를 오름차순 정렬 해준다. 여기서 2가 포함이 된다.  

 

 

다음은 31524의 다음 순열을 위의 공식에 따라 구해본다. 1 ~ 4과정은 쉽게 이해가 될 것이다. 5만 다시 본다면, 3 5 4 2 1 -> 5 3 4 2 1 로 자리가 바뀌었다. 막대기를 하나 그리고 다시 살펴보자면, 3 | 5 4 2 1 -> 5 | 3 4 2 1 로 바뀌었고, 3을 기준으로 우측 부분의 모든 수(3 4 2 1)를 오름차순으로 정렬해준다. 그러면 31524의 다음 순열(next permutation)51234로 완성이 된다. 

 

 

문제 연습

백준 10972번 다음 순열 : https://www.acmicpc.net/problem/10972

 

지금까지 배운 Next Permutation을 활용하여 문제를 풀어본다. 응용이 필요하지 않고, 기본 내용을 그대로 적용하기만 하면 된다. 

 

JAVA

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

public class Main {
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {

        // init
        input();

        // solve
        nextPermutation();
    }

    private static void input() throws IOException {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];

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

    private static void nextPermutation() {
        int flagIdx = N - 1;
        // 1. 오른쪽 맨 뒤에서 부터, Ai-1 < Ai인 수 찾기
        while (flagIdx > 0 && arr[flagIdx - 1] > arr[flagIdx]) {
            flagIdx--;
        }

        if (flagIdx == 0) {
            System.out.print(-1);
            return;
        }

        // 2. Ai-1 과 Ai 를 기준으로 left, right 공간 나눠서 생각하고,
        // 3. left의 맨 오른쪽 인덱스(flagIdx)의 수를 기준으로, right의 맨 오른쪽에서 왼쪽으로 탐색했을 때 큰 수를 찾는다.
        int rightMaxIdx = N - 1;
        while (rightMaxIdx > flagIdx && arr[flagIdx - 1] > arr[rightMaxIdx]) {
            rightMaxIdx--;
        }

        int temp = arr[flagIdx - 1];
        arr[flagIdx - 1] = arr[rightMaxIdx];
        arr[rightMaxIdx] = temp;

        Arrays.sort(arr, flagIdx, N);

        StringJoiner sj = new StringJoiner(" ");
        for (int i = 0; i < N; i++) {
            sj.add(String.valueOf(arr[i]));
        }

        System.out.print(sj);
    }
}

 

 

 

Python

import sys

input = sys.stdin.readline


# 다음 순열을 구하는 복잡도는 O(N)
# 전체 순열을 모두 구하면 O(N! * N)

def next_permutation():
    global arr
    idx = n - 1
    while idx > 0 and arr[idx - 1] > arr[idx]:
        idx -= 1
    if idx <= 0: return False

    rightMaxIdx = n - 1
    while rightMaxIdx > idx and arr[rightMaxIdx] < arr[idx - 1]:
        rightMaxIdx -= 1

    arr[idx - 1], arr[rightMaxIdx] = arr[rightMaxIdx], arr[idx - 1]

    arr = arr[:idx] + sorted(arr[idx:])
    return True


n = int(input())
arr = list(map(int, input().split()))
if next_permutation():
    print(' '.join(map(str, arr)))
else:
    print(-1)

티스토리툴바