알고리듬 - 순열

프로그래머스 2단계에 순열을 활용하는 완전탐색 문제가 보여서 이에 대한 전반적인 내용을 정리하고자 한다.

 

순열(Permutation)

순열이란 서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수이다.

순열의 계산은 아래와 같이 한다.

 

 

 

순열의 개수 계산 구현

식만 알고 있으면 순열의 수 계산을 구현하는 것은 어렵지 않다.

public class Main {
    public static void main(String[] args) {
        System.out.println(calculatePermutation(10, 3));
    }

    static int calculatePermutation(int n, int r) {
        int sum = 1;
        for(int i = 0; i < r; i++)
            sum *= n--;
        return sum;
    }
}

 

 

순열 경우 구현

이번엔 숫자 입력 값에 따라 순열의 모든 경우를 출력하는 코드를 구현해 보자.

예를 들어 3을 입력하면 아래와 같이 동작한다. 

 

구현은 DFS를 활용했다. 코드와 결과는 아래와 같다.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int input = 3;
        boolean[] visited = new boolean[input];
        int[] permutation = new int[input];
        printPermutation(input, 0, permutation, visited);
    }

    static void printPermutation(int n, int count, int[] permutation, boolean[] visited) {
        if(count == n) {
            System.out.println(Arrays.toString(permutation));
            return;
        }

        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                permutation[count] = i + 1;
                printPermutation(n, count + 1, permutation, visited);
                visited[i] = false;
            }
        }
    }
}

아래는 input = 5일 때의 결과이다. 올바르게 동작함을 확인할 수 있다.

보고 있자니 어지러워서 접어 둔다.

 

input은 3에서 5로 2만큼 증가했는데 출력 개수는 6에서 120으로 114만큼 증가했다.

O(n!)의 시간복잡도를 가지기 때문에 순열을 활용하는 완전탐색 문제는 대부분 n의 값이 작다.

 

막상 구현하고 보니 할만하다는 생각이 들었다. 지레 어렵겠거니 생각한 것에 대한 아쉬움이 있다.