[Argorithm] 다음 순열 알고리즘(prev_permutation Argorithm)

📝 개요

다음 순열 알고리즘은 현재 순열보다 큰 다음 순열을 찾는 알고리즘이다.

 

[1,2,3]이 있다고 해보자 해당 숫자의 모든 가능한 순열은 아래와 같다.

 

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

 

📝 동작 방식

다음 순열 알고리즘은 다음 순열을 얻으려면 피벗 포인트를 사용한다. 

1.  오른쪽에서 왼쪽으로 가면서, 현재 요소( i )와 바로 오른쪽 요소( i + 1 )를 찾는다.  i < i + 1인 경우, i가 피벗포인트가 된다.
2. 피벗 포인트보다 오른쪽에 위치한 요소들 중에서 피벗 포인트의 값보다 큰 가장 작은 값을 찾는다. 
3. 피벗 포인트와 찾은 값을 교환한다.
4. 피벗  포인트의 오른쪽부터 끝까지의 요소들을 오름차순로 정렬한다. 여기서 주목할 점은 교환 동작 후 피벗포인트의 오른족 요소들이 내림차순으로 정렬되어 있다는 점이다. 

1. 초기 순열

• [2,5,1,4,3]의 초기 배열로 시작해보자

2. 피벗 포인트를 찾는 과정

• 오른쪽부터 왼쪽으로 가면서 i < i + 1인 피벗 포인트를 i를 찾는다.

3. 피벗 포인트의 오른쪽 요소들 중에서 피벗 포인트보다 큰 가장 작은 값을 찾는다.

4. 피벗 포인트와 찾은 값을 교환한다. 

 

5. 피벗 포인트의 오른쪽 요소들을 오름차순으로 정렬하면 다음 순열이 된다. 

📝 다음 순열 구현

import java.io.*;
import java.util.*;

class Main {
    static int arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int 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());
        }

        solve();
    }
	//다음 순열
    public static void solve() {
        int i = arr.length - 2;

        // 피벗 포인트 찾기
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }

        // 만약 가장 큰 순열이면 -1 출력
        if (i < 0) {
            System.out.println(-1);
            return;
        }

        // arr[i]보다 큰 가장 작은 수 찾기
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }

        // arr[i]와 arr[j]를 교환
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        // arr[i+1]부터 arr[n-1]까지의 순서 뒤집기
        Arrays.sort(arr, i + 1, arr.length);

        // 다음 순열 출력
        for (int x = 0; x < arr.length; x++) {
            System.out.print(arr[x] + " ");
        }
        System.out.println(); 
    }
}

 

 

 

📝 이전 순열 구연

import java.io.*;
import java.util.*;

class Main {
    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int 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());
        }

        solve();
    }

    public static void solve() {
        int i = arr.length - 2;

        // 피벗 포인트 찾기
        while (i >= 0 && arr[i] <= arr[i + 1]) {
            i--;
        }

        // 가장 작은 순열인 경우 -1 출력
        if (i < 0) {
            System.out.println(-1);
            return;
        }

        // arr[i]보다 큰 가장 작은 수 찾기
        int j = arr.length - 1;
        while (arr[j] >= arr[i]) {
            j--;
        }

        // arr[i]와 arr[j]를 교환
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        // arr[i+1]부터 배열의 끝까지 내림차순으로 정렬
        reverse(arr, i + 1, arr.length);

        // 이전 순열 출력
        for (int x = 0; x < arr.length; x++) {
            System.out.print(arr[x] + " ");
        }
        System.out.println(); // 배열 출력 후 줄 바꿈
    }

    // 배열의 특정 범위를 뒤집는 메서드
    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end - 1];
            arr[end - 1] = temp;
            start++;
            end--;
        }
    }
}

 

📝 모든 순열