[백준알고리즘] 15663 - N과 M (9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

문제는 위와 같으며 이 문제는 일반 수열에서 중복된 값을 제거하는 문제입니다. n개 중 m개의 수를 선택하여 하나의 문자열로 만든 뒤, 해당 문자가 이미 선택된 수들의 문자 모음인 Set에 저장되어 있지 않다면 저장하고 출력하는 방식으로 문제를 해결하였습니다.

 

자바 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    private static Set<String> answer = new HashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(nums);

        permutation(nums, new int[n], new boolean[n], n, m, 0);
    }

    private static void permutation(int[] nums, int[] selected, boolean[] isSelect, int n, int m, int depth) {
        if (depth == m) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < depth; i++) {
                sb.append(selected[i]).append(" ");
            }

            if (!answer.contains(sb.toString())) {
                answer.add(sb.toString());
                System.out.println(sb);
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!isSelect[i]) {
                isSelect[i] = true;
                selected[depth] = nums[i];
                permutation(nums, selected, isSelect, n, m, depth + 1);
                isSelect[i] = false;
            }
        }
    }
}