알고리즘)브루트 포스(Brute Force)와 순열(permutation)

# 브루트 포스 : 모든 경우의 수를 고려하는 방식이다.

# 순열 : 임의의 수열을 각자 다른 순서로 섞어 세우는 경우의 수들을 의미

 - 순서를 고려하는 문제에 사용되기 좋다.
 - 크기가 n인 수열에서 서로 다른 순열은 총 n!개가 있다.
ex) A = [1, 2, 3]
순열들 : 123, 132, 213, 231, 312, 321 (사전순으로 나열함)
모든 순서를 다 고려해야하는 문제에서 순열이 사용된다. 

(그러므로 순열을 사용하는 것은 브루트 포스의 일종이라고 할 수 있다.)

순열을 문제에 응용하기 위해서는 특정 순열에서 다음 순열을 구하는 알고리즘이 필요하다.
C++과 파이썬의 경우에는 다음 순열을 구하는 알고리즘이 자체적으로 구현되어 있지만,  자바에는 없다.

(자바에서는 직접 구현해주어야 한다.)

ex) N=4이고 A = [1, 2, 3, 4]이면 
순열은 총 4!(24)개
1234 2134 ...
1243 2143
1324 2314
1342 2341
1423 2413
1432 2431

순열들은 앞자리수부터 사전순으로 나열됨.
앞이 1인 모든 경우 -> 앞이 2인 모든 경우 -> 앞이 3인 모든 경우 -> ...

 

# 첫번째 순열과 마지막 순열의 특성
첫 순열 : 1234 - 오름차순임
마지막 순열 : 4321 - 내림차순임

ex )  7236541의 다음 순열 구하기 
723 / 6541 - 6541은 내림차순임 (내림차순이라는 것은 해당 자리에서 시작 기준 마지막 순열이라는 뜻)
그러므로 해당 순열의 다음 순열은 72?????다 된다.
다음 순열은 3 뒤에 위치한 수 중 3과 가장 적은 차이로 큰 수가 ? 중 첫자리에 오게 된다.
3 뒤의 6541 중 위 조건에 해당하는 수는 4이다.
(이를 찾는 시간복잡도 = O(N))
마지막 순열 다음은 첫 순열이 오게 되므로
72 / 4 / 1356 (1356은 오름차순으로 해당 자리 기준의 첫 순열이다.)
(첫 순열 만드는 것도 시간복잡도가 O(N)이다.)

그러므로 7236541의 다음 순열은 7241356이다.

위 과정을 4개의 단계들로 정리하면 (i는 내림차순 부분의 첫 자리 인덱스라고 할 때)

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다. 

   (뒤에 내림차순의 수만 남는 첫번째 자리를 구하기)

2. j>=i이면서 A[j]>A[i-1]을 만족하는 가장 작은 j를 찾는다. 

   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 큰 값을 찾기)

3. A[i-1]과 A[j]를 swap한다.

4. A[i]부터 순열을 뒤집는다. 

   (i자리부터 오름차순으로 만들어줌 -> 해당 자리 기준 첫 순열로 만듬)

1과 2는 O(n), 3은 O(1), 4는 O(n)
그러므로 총 시간 복잡도는  O(n) + O(n) + O(n) + O(n) = O(n)이다.

모든 순열을 구하기 위해서는 첫 순열부터 마지막 순열에 다다를 때까지(n!-1번) 위 알고리즘(O(n))을 반복해주어야 한다.
그러므로 모든 순열을 구하는 총 시간복잡도는 O(n*n!)이 된다.

 

팩토리얼 값은

3! = 6,

... ,

10! = 3,628,800 (3천만~)

11! = 39,916,800 (약 4억)

이므로 

순열은 수열의 크기의 입력이 11보다 작은 경우에 주로 사용된다.

(이보다 크면 모든 순열을 고려하는데 이미 적어도 4초 이상이 걸리므로 좋지 않음)

 

# 다음 순열을 구하는 알고리즘 (마지막 순열이 입력으로 들어오면 -1 출력)

 - next_permutation 메소드가 해당 알고리즘을 구현한 메소드이다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = sc.nextInt();
        int[] ans = next_permutation(seq);
        if (ans == null) System.out.println(-1);
        else {
            for (int i=0;i<ans.length;i++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }

    // 다음 순열(permutation) 구하는 알고리즘(메소드)
    // 1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 내림차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j>=i이면서 A[j]>A[i-1]을 만족하는 가장 작은 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 큰 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 오름차순으로 만들어줌 -> 해당 자리 기준 첫 순열로 만듬)
    static int[] next_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] < seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int minJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (indexI < 1) break;
            if (seq[indexI-1] < seq[j]) {
                if (minJ == -1 || seq[j] < minJ) {
                    minJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        Arrays.sort(tempArr);
        for (int i=indexI;i<seq.length;i++) seq[i] = tempArr[i-indexI];

        return seq;
    }
}

# 이전 순열을 구하는 알고리즘 (다음 순열을 구하는 알고리즘에서 부등호들을 모두 반대로 바꾸어주면 됨)

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = sc.nextInt();
        int[] ans = prev_permutation(seq);
        if (ans == null) System.out.println(-1);
        else {
            for (int i=0;i<ans.length;i++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }

    // 이전 순열(permutation) 구하는 알고리즘(메소드)
    // 다음 순열을 구하는 알고리즘에서 부들호들만 반대로 바꾸어서 구현해주면 된다.
    // 1. A[i-1] > A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 오른차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j<=i이면서 A[j]<A[i-1]을 만족하는 가장 큰 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 작은 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 내림차순으로 만들어줌 -> 해당 자리 기준 마지막 순열로 만듬)
    static int[] prev_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] > seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int maxJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (seq[indexI-1] > seq[j]) {
                if (maxJ == -1 || seq[j] > maxJ) {
                    maxJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        int k = seq.length-indexI-1;
        for (int i=indexI;i<seq.length;i++) {
            seq[i] = tempArr[k];
            k-=1;
        }
        return seq;
    }
}