[BOJ/Java] N과 M (12) (15666)

N과 M (12) (15666)

1. 문제 분석

문제 개요

• 주어진 N개의 숫자 중에서 M개의 숫자를 중복을 허용하여 선택하고, 선택된 숫자들이 오름차순으로 정렬된 모든 경우를 출력하는 문제이다.
• 중복된 수열은 제거하며, 사전 순서대로 결과를 출력해야 한다.

입력 형식

• 첫째 줄에 두 정수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 정수가 주어진다. 이 정수들은 공백으로 구분되어 있다.

출력 형식

• M개의 숫자를 중복을 허용하여 선택한 모든 경우를 사전 순서대로 출력한다. 각 수열은 한 줄에 하나씩 출력되며, 중복된 수열은 한 번만 출력된다.

2. 알고리즘 종류

• 이 문제는 조합 문제로, 중복을 허용하여 M개의 숫자를 선택하고, 선택된 수열이 오름차순으로 정렬되도록 한다.

3. 주요 부분 및 코드 작성 방법

1. 입력 처리 및 배열 초기화

• 입력받은 숫자들을 정렬하고, 중복 조합을 생성하기 위한 배열과 결과를 저장할 Set을 준비한다.

2. 조합 생성

• 재귀 함수를 사용하여 중복을 허용하여 M개의 숫자를 선택하며, 선택된 숫자들이 오름차순으로 정렬되도록 한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 배열 초기화
  • BufferedReader와 StringTokenizer를 사용하여 입력을 처리하고, 숫자 배열을 정렬하여 조합 생성을 준비한다.
• BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader 객체 생성 StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력 처리 N = Integer.parseInt(st.nextToken()); // 숫자의 개수 N 입력 M = Integer.parseInt(st.nextToken()); // 선택할 숫자의 개수 M 입력 nums = new int[N]; // 입력된 숫자를 저장할 배열 생성 numbers = new int[M]; // 조합을 저장할 배열 생성 answer = new LinkedHashSet<>(); // 결과를 저장할 LinkedHashSet 객체 생성 (중복 제거 및 순서 유지) st = new StringTokenizer(br.readLine()); // 두 번째 줄 입력 처리 for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 숫자 배열에 입력값 저장 Arrays.sort(nums); // 입력된 숫자를 오름차순으로 정렬
• 조합 생성 호출 및 결과 출력
  • comb 함수를 호출하여 모든 가능한 조합을 생성하고, Set에 저장된 결과를 출력한다.
• comb(0); // 조합 생성 함수 호출 answer.forEach(System.out::println); // 결과 출력

(2) 조합 생성 함수 (comb)

• 중복을 허용하여 M개의 숫자를 선택하고 오름차순으로 정렬된 경우 생성
  • 현재 인덱스가 M에 도달하면, 현재 조합을 StringBuilder로 생성하고 Set에 추가하여 중복된 수열이 포함되지 않도록 한다.
  • 그렇지 않으면, 배열 nums의 숫자들을 순서대로 선택하여 중복을 허용한 모든 조합을 생성하고, 재귀 호출을 통해 모든 가능한 경우를 탐색한다.
• public static void comb(int idx) { if (idx == M) { StringBuilder sb = new StringBuilder(); // 현재 조합을 저장할 StringBuilder 객체 생성 for (int i : numbers) sb.append(i + " "); // 현재 조합을 결과에 추가 answer.add(sb.toString()); // Set에 추가하여 중복 방지 } else { for (int i = 0; i < N; i++) { if (idx == 0 || numbers[idx - 1] <= nums[i]) { // 오름차순 유지 확인 numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장 comb(idx + 1); // 다음 인덱스로 재귀 호출 } } } }

5. 전체 코드

import java.io.*;
import java.util.*;

public class BOJ15666 {
    static int N, M;
    static int[] numbers, nums;
    static Set<String> answer; // 중복을 방지하고 사전 순서를 유지하기 위해 LinkedHashSet 사용

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader 객체 생성
        StringTokenizer st = new StringTokenizer(br.readLine()); // 첫 번째 줄 입력 처리
        N = Integer.parseInt(st.nextToken()); // 숫자의 개수 N 입력
        M = Integer.parseInt(st.nextToken()); // 선택할 숫자의 개수 M 입력
        nums = new int[N]; // 입력된 숫자를 저장할 배열 생성
        numbers = new int[M]; // 조합을 저장할 배열 생성
        answer = new LinkedHashSet<>(); // 결과를 저장할 LinkedHashSet 객체 생성 (중복 제거 및 순서 유지)

        st = new StringTokenizer(br.readLine()); // 두 번째 줄 입력 처리
        for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 숫자 배열에 입력값 저장
        Arrays.sort(nums); // 입력된 숫자를 오름차순으로 정렬

        comb(0); // 조합 생성 함수 호출
        answer.forEach(System.out::println); // 결과 출력
    }

    public static void comb(int idx) {
        if (idx == M) {
            StringBuilder sb = new StringBuilder(); // 현재 조합을 저장할 StringBuilder 객체 생성
            for (int i : numbers) sb.append(i + " "); // 현재 조합을 결과에 추가
            answer.add(sb.toString()); // Set에 추가하여 중복 방지
        }
        else {
            for (int i = 0; i < N; i++) {
                if (idx == 0 || numbers[idx - 1] <= nums[i]) { // 오름차순 유지 확인
                    numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장
                    comb(idx + 1); // 다음 인덱스로 재귀 호출
                }
            }
        }
    }
}