백준 - 15649 N과 M (1) [순열]

 

15649번: N과 M (1)

 

1. 문제 요약

1부터 N까지의 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다.

 

2. 접근 방법

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

 

3. 파이썬

3 - 1. 재귀함수 이용

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())

def solution(num: int, arr: list):
    if num == m:
        print(*arr)
    else:
        for i in range(1, n + 1):
            if i in arr:
                continue
            solution(num + 1, arr + [i])

solution(0, [])

 

3 - 2. itertools.permutations 함수 이용

itertools 모듈의 permutions 함수를 이용하여 순열을 손쉽게 생성할 수 도 있습니다.

from itertools import permutations
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())

for p in permutations(list(range(1, n+1)), m):
    print(*p)

 

4. 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int m;
    static int[] arr;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        visit = new boolean[n];

        solution(0);

        System.out.println(sb);
    }

    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] = i + 1;
                solution(depth + 1);
                visit[i] = false;
            }
        }
    }
}