백준 - 15654 N과 M (5) [순열]

 

15654번: N과 M (5)

 

1. 문제 요약

주어진 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다.

출력 시 오름차순으로 정렬하여야 합니다.

 

2. 접근 방법

순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다.

• 입력받은 숫자들을 오름차순 정렬
• 재귀함수를 이용하여 순열 생성

 

3. 파이썬

from sys import stdin
input = stdin.readline

def solution(depth: int):
    if depth == M:
        print(' '.join(map(str, arr)))
        return

    for i in range(N):
        if not visit[i]:
            visit[i] = True
            arr[depth] = nums[i]
            solution(depth + 1)
            visit[i] = False

N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
visit = [False] * N
arr = [0] * M

solution(0)

 

4. 자바

static int N, M;
static int[] nums; // 입력받은 숫자배열, 오름차순 정렬해야함
static int[] arr; // 정답을 입력할 배열
static boolean[] visit; // 방문 여부
static StringBuilder sb = new StringBuilder();

static void solution(int depth) {
    if (depth == M) {
        for (int i : arr) {
            sb.append(i).append(' ');
        }
        sb.append('\n');
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!visit[i]) {
            visit[i] = true;
            arr[depth] = nums[i];
            solution(depth + 1);
            visit[i] = false;
        }
    }
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/15654.%E2%80%85N%EA%B3%BC%E2%80%85M%E2%80%85%EF%BC%885%EF%BC%89