memostack
article thumbnail
블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
반응형

순열

[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)

본 문제는 백준 알고리즘(https://www.acmicpc.net/)에게 있습니다. 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서..

memostack.tistory.com

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

 

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

본 문제는 백준 알고리즘(https://www.acmicpc.net/)에게 있습니다. 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서..

memostack.tistory.com

 

반응형
블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
profile

memostack

@bluemiv_mm

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!