[Algorithm] Next Permutation 알고리즘

화이팅

개요

백준 문제를 풀다가 6443번 애너그램 만들기 문제를 백트래킹으로 풀던 중 너무 많은 경우의 수가 존재해서 자바의 힙 메모리가 오바되서 문제를 해결하지 못했습니다.

그래서 어떻게 풀면 될까 고민하다가 Next Permutation 알고리즘이 존재한다는 것을 알았고 문자나 숫자를 나열하는 문제를 더 효율적으로 해결할 수 있을 것 같아서 공부하고 작성합니다.

6443번: 애너그램

 

본론

Next Permutation 알고리즘은 현재 나열된 숫자나 문자의 바로 다음 수열을 찾는 문제입니다.

알고리즘의 방식은 다음과 같습니다.

1. 수열의 뒤부터 탐색하면서 뒤에서 봤을 때 오름차순이 깨지는 인덱스 i 를 찾습니다.
   • ex) 1 3 2 1 이라는 수열이 존재할 때, 뒤에서 봤을 때 오름차순이 깨지는 부분은 3다음의 1이 됩니다.
2. 수열의 뒤부터 탐색하면서 앞에서 찾은 인덱스 i보다 큰 인덱스 j 를 찾습니다.
   • ex) 1 3 2 1 이라는 수열이 존재할 때, 0번 인덱스보다 큰 값은 2입니다. 따라서 j는 2가 됩니다.
3. i와 j를 swap하고 i+1부터 마지막 인덱스까지의 값을 오름차순 정렬합니다. 또는 i+1부터 마지막 인덱스까지의 값들을 reverse 합니다. (이미 i+1까지는 오름차순이기 때문에 뒤집으면 정렬된다.)
   1. ex) 2 3 1 1 (swap) → 2 1 1 3 (오름차순 정렬)
   2. ex) 2 3 1 1 (swap) → 2 1 1 3 (1번 인덱스와 3번 인덱스를 swap)

따라서 1 3 2 1의 사전순으로 다음 순번은 2 1 1 3이 됩니다.

코드로 작성하면서 다시 보도록 하겠습니다.

1. 수열의 뒤부터 탐색하면서 뒤에서 보았을 때 오름차순이 깨지는 인덱스 i를 찾는다.

int i = A.length-2;

// 뒤에서 부터 탐색하면서 오름차순이 깨지는 부분을 찾는다.
while(i >= 0 && A[i] >= A[i+1])
    i--;

if(i == -1) return; // 마지막 수열

i인덱스와 i+1 인덱스를 비교하면서 i가 i+1보다 작아질 때 반복을 종료해서 찾는다.

• 이때 만약 모든 수가 오름차순이라면(뒤에서 부터) 마지막 수열이기 때문에 종료한다.

2. 수열의 뒤부터 탐색하면서 앞에서 찾은 인덱스 i보다 큰 인덱스 j를 찾습니다.

int j = A.length-1;

// 뒤에서부터 탐색하면서 i보다 큰 j를 찾는다.
while (A[i] >= A[j])
    j--;

i가 j보다 클때 까지 반복하면서 값을 찾습니다.

3. i와 j의 값을 스왑하고 i+1번 인덱스부터 마지막 인덱스까지의 값을 정렬합니다.

// i+1부터 정렬한다. (i+1부터 순열의 끝까지 뒤에서 오름차순이기 때문에 양 값을 스왑하면 된다.)
j = A.length-1;
i++;
while (i < j){
    swap(A, i++, j--);
}

📌 전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] A = br.readLine().toCharArray();
        int i = A.length-2;
        int j = A.length-1;

        // 뒤에서 부터 탐색하면서 오름차순이 깨지는 부분을 찾는다.
        while(i >= 0 && A[i] >= A[i+1])
            i--;

        if(i == -1) return; // 마지막 순열

        // 뒤에서부터 탐색하면서 i보다 큰 j를 찾는다.
        while (A[i] >= A[j])
            j--;

        // 두 값을 스왑한다.
        swap(A, i, j);

        // i+1부터 정렬한다. (i+1부터 순열의 끝까지 뒤에서 오름차순이기 때문에 양 값을 스왑하면 된다.)
        j = A.length-1;
        i++;
        while (i < j){
            swap(A, i++, j--);
        }

        for(int x=0; x<A.length; x++){
            System.out.print(A[x]);
        }
    }
    public static void swap(char[] arr, int i, int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

결론

하면서 정말 알고리즘은 끝도없이 많고 아직 부족한 것이 많다고 느꼈습니다.

위의 코드로 다음 수열이 잘 나오는 것을 볼 수 있었습니다.!