[BOJ/Java] N과 M (8) (15657)

N과 M (8) (15657)

1. 문제 분석

문제 개요

• 주어진 N개의 숫자 중에서 M개의 숫자를 중복을 허용하여 비내림차순(오름차순이거나 동일한 순서)으로 나열하는 모든 경우를 출력하는 문제이다. 숫자는 오름차순으로 정렬된 상태로 출력해야 한다.

입력 형식

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

출력 형식

• M개의 숫자를 중복을 허용하여 비내림차순으로 나열한 모든 경우를 오름차순으로 출력한다.

2. 알고리즘 종류

• 이 문제는 중복 조합을 사용하여 가능한 모든 경우를 생성하는 문제이다. 숫자를 중복하여 나열할 수 있는 모든 경우를 생성하는 조합 문제로, 비내림차순 조건을 만족해야 한다.

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

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

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

2. 중복 조합 생성

• 재귀 함수를 사용하여 비내림차순 조건을 만족하는 중복 조합을 생성하고, 결과를 StringBuilder에 저장한다.

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]; // 조합을 저장할 배열 생성 st = new StringTokenizer(br.readLine()); // 두 번째 줄 입력 처리 for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 숫자 배열에 입력값 저장 Arrays.sort(nums); // 입력된 숫자를 오름차순으로 정렬
• 중복 조합 생성 호출 및 결과 출력
  • comb 함수를 호출하여 모든 가능한 중복 조합을 생성하고, StringBuilder를 사용하여 결과를 출력한다.
• comb(0); // 중복 조합 생성 함수 호출 System.out.println(sb); // 결과 출력

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

• 중복 조합 생성
  • 현재 인덱스가 M에 도달하면, 현재 조합을 StringBuilder에 추가한다. 그렇지 않으면, 배열 nums의 모든 숫자를 현재 인덱스에 배치하고, 다음 인덱스로 재귀 호출하여 모든 가능한 중복 조합을 생성한다. 이때, 이전에 선택한 숫자와 같거나 큰 숫자만 선택하여 비내림차순 조건을 유지한다.
• public static void comb(int idx) { if (idx == M) { for (int i : numbers) sb.append(i + " "); // 현재 조합을 결과에 추가 sb.append("\n"); // 줄바꿈 추가 return; } 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 BOJ15657 {
    static int N, M;
    static int[] nums, numbers;
    static StringBuilder sb = new StringBuilder(); // 결과를 저장할 StringBuilder 객체 생성

    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]; // 조합을 저장할 배열 생성

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

        comb(0); // 중복 조합 생성 함수 호출
        System.out.println(sb); // 결과 출력
    }

    public static void comb(int idx) {
        if (idx == M) {
            for (int i : numbers) sb.append(i + " "); // 현재 조합을 결과에 추가
            sb.append("\n"); // 줄바꿈 추가
            return;
        }
        else {
            for (int i = 0; i < N; i++) {
                if (idx == 0 || numbers[idx - 1] <= nums[i]) { // 비내림차순 조건 확인
                    numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장
                    comb(idx + 1); // 다음 인덱스로 재귀 호출
                }
            }
        }
    }
}