순열 을 다양하게 돌아보자.

Ps 해결 과정 중에 몇개중에 몇개를 선택하세요 등의 해결해야 하는 경우가 간간히 발생하게 된다.

 

 

왼쪽 과 같이 정해진 배열 안에서 가능한 경우의 수를 모두 구해서 찾고자 하는 값을 리턴할떄 보통 순열 의 방법을 생각하고 구현하려고 한다. 보이는 것처럼 순열 에는 미디움 레벨의 중간 난이도로 측정을 하고 있다. ps를 하면서 많이 사용은 안하지만 가끔 나오면 헷갈려서 찾아보곤 하는데 이번에 정리를 해보자.

 

 

 

 

1. 재귀를 이용한 방법 , 이 방법을 항상 제일 먼저 떠올리고 사용하는것 같다.

[1,2,3] 에 대해 3 자리수 순열을 구해 본다면 3! 해서 6을 쉽게 떠올릴수 있다. 코드를 구현하려고 하면 막막한데 어떻게 하면 될까?

위의 그림을 타고 내려간후 깊이가 3이라면 ? 출력 을 하거나 멈춰주는 재귀 의 조건을 걸어주면 된다. 코드를 보자.

public void main() {
        int[] arr = { 1, 2, 3 };
        int[] out = new int[3];
        boolean[] visit = new boolean[3];
        System.out.println("=== Permutation ===");
        permutation_fisrt(arr, out, visit, 0);
    }

public void permutation_fisrt(int[] arr, int[] out, boolean[] visit, int depth) {
        if (depth == out.length) {
            System.out.print(Arrays.toString(out) + " ");
            return;
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (visit[i] != true) {
                    visit[i] = true;
                    out[depth] = arr[i];
                    permutation_fisrt(arr, out, visit, depth + 1);
                    visit[i] = false;
                }
            }
        }

    }

출력 결과 : [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

위의 그림과 동일한 결과가 나온다. 현재의 깊이와 내가 출력하고자 하는 개수가 같다면 재귀를 멈춰주는 것이 키 포인트이다. 

함수의 재귀 호출 이후 visit[i] 를 false 해주는 이유가 뭘까 ?

visit 은 모든 재귀 호출시에 공유 되어지는 동일한 변수이다. 따라서 현재 재귀 실행중인 수를 사용후 다시 반납을 해주어야 현재 레벨에서 진행되는 다른 재귀에 영향을 주지않는다. 만약 저 다시 숫자를 반납하지 않는다면 [1,2,3] 의 하나의 경우만 출력하게 된다. 재귀의 마지막 레벨에 도달하면 다시 위의 레벨로 거슬러 올라가는것을 생각해 본다면 조금 더 생각하기 쉽다.

 

2. 인덱스 순서를 이용해 위치를 바꿔주는 방법

재귀의 깊이에 따라 인덱스 보다 높은 인덱스 들의 배열 순서를 바꿔주는 것이다. 그림으로 본다면 아래와 같다

public void permutation_second(int[] arr, int out[], int depth) {
        if (depth == out.length) {
            System.out.print(Arrays.toString(out) + " ");
            return;
        } else {
            for (int i = depth; i < arr.length; i++) {
                out[depth] = arr[i];
                swap(arr, depth, i);
                permutation_second(arr, out, depth + 1);
                swap(arr, depth, i);
            }
        }
    }

    public void swap(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }

출력결과: [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]

여기서 주의할점은 i 가 깊이 와 동일하다, 깊이 부터 교체를 하면 깊이보다 큰 숫자를 가져다 교체를 하게되는것이다. 그림과 동일하게 구현되어 있다.

 

3.비트마스크 를 이용한 해법

이 해법 은 릿코드 순열문제를 풀고 디스커스 를 보다 찾게된 풀이이다.

자리수 별로 비트를 이용해 1,0 을 이용해 사용하고 사용하지 않은것을 기록하는 방법이다.

ex) 0 & 0 => 0 이기 떄문에 이건 사용안한것이다, 그것을 out 에 등록을 해주고, 0 | 1<<0 을 이용해 1 값을 다음 연산에 넣어주는것이다.

public void permutation_third(int[] arr, int out[], int depth, int flag) {
        if (depth == out.length) {
            System.out.print(Arrays.toString(out) + " ");
            return;
        } else {
            for (int i = 0; i < arr.length; i++) {
                if ((flag & 1 << i) != 0)
                    continue;
                out[depth] = arr[i];
                permutation_third(arr, out, depth + 1, flag | 1 << i);
            }
        }
    }

flag | 1<<i 이부분이 바로 방문 처리를 해주는 부분이다. 횟수를 거듭할수록 쉬프트 에 따라 이진수 단위가 늘어나 깊이에 따라 flag 의 단위도 3자리 가된다. 신박한 방법이였다.

 

제일 재밌는 성능 측정을 해보자.

차례대로 1,2,3 의 시간순이다. 출력을 하지않는다면 그렇게 유의미한 시간차이는 나지 않는것 같다.

출력을 제외하고 여러번 테스트 해본결과, 배열의 수가 적은 단위라면 1000 단위가 넘어간다면 스왑 을 이용한 방식이 가장 빠르고 만약 100개중 100개의 순열을 구한다면 비트마스크가 제일 빠르다.

본인이 편한 방법중 하나를 사용하면 된다. 

 

코드 전문

import java.util.stream.IntStream;
import java.util.*;

public class PermutationTestDrive {
    public static void main(String[] args) {
        Permu p = new Permu();
        int[] arr = IntStream.range(1, 101).map(x -> Integer.valueOf(x)).toArray();
        int cnt = 21;
        int[] out = new int[3];
        boolean[] visit = new boolean[arr.length];
        // 1번
        Timer t1 = new Timer();
        p.permutation_fisrt(arr, out, visit, 0);
        t1.printDiffer();
        // 2번
        out = new int[3];
        Timer t2 = new Timer();
        p.permutation_second(arr, out, 0);
        t2.printDiffer();
        // 3번
        out = new int[3];
        Timer t3 = new Timer();
        p.permutation_third(arr, out, 0, 0);
        t3.printDiffer();
    }
}

class Timer {
    long beforeTime;

    Timer() {
        this.beforeTime = System.currentTimeMillis();
    }

    void printDiffer() {
        long afterTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("✅ 소요시간 " + (afterTime - beforeTime) + " ms");
    }
}

class Permu {
    public void main() {
        int[] arr = { 1, 2, 3 };
        int[] out = new int[3];
        boolean[] visit = new boolean[arr.length];
        System.out.println("=== Permutation ===");
        permutation_fisrt(arr, out, visit, 0);
        System.out.println();
        out = new int[3];
        System.out.println("=== Permutation ===");
        permutation_second(arr, out, 0);
        System.out.println();
        System.out.println("=== Permutation ===");
        out = new int[3];
        permutation_third(arr, out, 0, 0);
    }

    public void permutation_fisrt(int[] arr, int[] out, boolean[] visit, int depth) {
        if (depth == out.length) {
            // System.out.print(Arrays.toString(out) + " ");
            return;
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (visit[i] != true) {
                    visit[i] = true;
                    out[depth] = arr[i];
                    permutation_fisrt(arr, out, visit, depth + 1);
                    visit[i] = false;
                }
            }
        }

    }

    public void permutation_second(int[] arr, int[] out, int depth) {
        if (depth == out.length) {
            // System.out.print(Arrays.toString(out) + " ");
            return;
        } else {
            for (int i = depth; i < arr.length; i++) {
                out[depth] = arr[i];
                swap(arr, depth, i);
                permutation_second(arr, out, depth + 1);
                swap(arr, depth, i);
            }
        }
    }

    public void swap(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }

    public void permutation_third(int[] arr, int out[], int depth, int flag) {
        if (depth == out.length) {
            // System.out.print(Arrays.toString(out) + " ");
            return;
        } else {
            for (int i = 0; i < arr.length; i++) {
                if ((flag & 1 << i) != 0)
                    continue;
                out[depth] = arr[i];
                permutation_third(arr, out, depth + 1, flag | 1 << i);
            }
        }
    }
}