Java 스택(Stack)을 이용해서 순열 구하기

순열

[1, 2, 3]의 순열은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이다.

이처럼 같은 원소가 중복되지 않고, 조합하여 나올 수 있는 모든 경우의 집합을 뜻한다.

 

재귀와 스택을 이용해서 순열을 생성하는 코드를 작성한다.

 

코드

아래 2가지 자료구조를 사용한다.

• Stack<Integer> stack: 원소를 담을 스택
• boolean[] chosen: 이미 포함한 원소를 구분하기 위한 불리안 배열

private static void search(Stack<Integer> stack) {
    if (stack.size() >= n) {
        System.out.println(stack.toString());
    } else {
        for(int i=1; i<=n; i++) {
            if(chosen[i]) continue; // 이미 뽑은 경우는 SKIP

            chosen[i] = true; // 포함
            stack.push(i);

            search(stack);

            chosen[i] = false; // 제외
            stack.pop();
        }
    }
}

 

전체 코드

import java.util.Stack;

public class Permutation {
    private static boolean[] chosen; // 뽑은 원소를 기록
    private static int n;

    public static void main(String[] args) {
        n = 3;
        chosen = new boolean[n+1];
        final Stack<Integer> stack = new Stack<>();
        search(stack);
    }

    private static void search(Stack<Integer> stack) {
        if (stack.size() >= n) {
            System.out.println(stack.toString());
        } else {
            for(int i=1; i<=n; i++) {
                if(chosen[i]) continue; // 이미 뽑은 경우는 SKIP

                chosen[i] = true; // 포함
                stack.push(i);

                search(stack);

                chosen[i] = false; // 제외
                stack.pop();
            }
        }
    }
}

실행결과

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

 

순열 문제 풀기

2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15649번 - N과 M(1) 순열 문제 (with Python3)

백준 Ex.15649번 - N과 M(1) 순열 문제 (with Python3)

2020/04/03 - [Algorithm/Beakjoon] - 백준 Ex.15650 - N과 M(2) - 순열 (with Python3)

백준 Ex.15650 - N과 M(2) - 순열 (with Python3)