백준 - 15654(N과 M (5))

문제 출처: https://www.acmicpc.net/problem/15654

문제

• N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

  • N개의 자연수 중에서 M개를 고른 수열

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

public class Main {

    private static int[] arr;
    private static int N, M;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(tokenizer.nextToken());
        M = Integer.parseInt(tokenizer.nextToken());

        arr = new int[N];
        tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        Arrays.sort(arr);

        permutation(new boolean[N], 0, new StringBuilder());

        System.out.println(sb);
    }

    private static void permutation(boolean[] isSelected, int cnt, StringBuilder cur) {
        if (cnt == M) {
            // 다 뽑음
            sb.append(cur).append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!isSelected[i]) {
                isSelected[i] = true;
                int temp = cur.length();
                cur.append(arr[i]).append(" ");
                permutation(isSelected, cnt + 1, cur);
                cur.setLength(temp);
                isSelected[i] = false;
            }
        }
    }

}

• 간단한 순열 문제였다.
• StringBuilder를 이용해서 출력했는데, 그냥 배열을 하나 만들어서 넣어도 될 것 같다.