[Java][조합][BOJ] 15663번 N과 M(9)

15663번 N과 M(9)

🤔 문제 이해하기

1. N개의 자연 수 중 M개를 아래 조건에 맞추어 선택
   • 사전 순으로 증가하는 순서
   • 중복되는 수열은 여러 번 선택 X
2. M ≤ N ≤ 8

⭐ 알고리즘

1. 수를 선택하는 문제 => 조합

2. 중복되는 수를 어떻게 확인할 건지가 관건

   • 사전 순으로 증가하는 순서
     - 주어진 N개 수를 오름차순으로 정렬
     - Link로 연결하여 순서 보장
   • 중복되는 수열은 여러 번 선택 X
     - Hashset의 특성 이용

   ⇒ LinkedHashSet을 사용하여 조건에 부합하는 M개의 숫자를 선택

💻 문제를 해결한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Main {

    static int n, m, arr[];
    static LinkedHashSet<String> hs = new LinkedHashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 정렬
        Arrays.sort(arr);

        // 숫자 선택
        combination(0, new int[m], new boolean[n]);

        // 출력
        for (String str : hs) {
            sb.append(str).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static void combination(int idx, int[] selected, boolean[] visited) {
        if (idx == m) {
            String str = "";
            for (int i = 0; i < m; ++i) {
                str += Integer.toString(selected[i]) + " ";
            }
            hs.add(str);
            return;
        }

        for (int i = 0; i < n; ++i) {
            if(visited[i]) continue;
            selected[idx] = arr[i];
            visited[i] = true;
            combination(idx + 1, selected, visited);
            visited[i] = false;
        }
    }

}