[BOJ/Java] N과 M(6) (15655)

N과 M(6) (15655)

1. 문제 분석

문제 개요

• 주어진 정수 배열에서 M개의 수를 선택하여 조합을 생성하고, 선택된 수들이 오름차순으로 정렬된 조합을 출력하는 문제이다.

입력 형식

• 첫 번째 줄에 배열의 크기 N과 조합의 크기 M이 주어진다.
• 두 번째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

출력 형식

• M개의 수로 이루어진 모든 가능한 조합을 오름차순으로 정렬하여 출력한다.

2. 알고리즘 종류

• 이 문제는 조합(Combination) 알고리즘을 사용하는 문제이다. 조합을 생성할 때, 중복 없이 M개의 숫자를 선택하고 오름차순으로 정렬된 조합을 출력해야 한다.

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

1. 조합 생성

• comb 함수를 사용하여 조합을 생성한다. 이 함수는 재귀적으로 호출되어 M개의 숫자가 선택될 때까지 조합을 생성한다.

2. 중복 방지 및 오름차순 유지

• 조합을 생성할 때 이전에 선택된 숫자보다 큰 숫자만을 선택하여 오름차순을 유지한다.

3. 정렬 및 출력

• 입력된 숫자를 정렬하여 오름차순 조합을 생성한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리
  • BufferedReader와 StringTokenizer를 사용하여 입력을 처리한다.
  • 배열의 크기와 조합의 크기를 입력받고, 정수를 배열에 저장한다.
• BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader 객체 생성 StringTokenizer st = new StringTokenizer(br.readLine()); // 입력 데이터 처리용 StringTokenizer 생성 N = Integer.parseInt(st.nextToken()); // 배열의 크기 N 입력 M = Integer.parseInt(st.nextToken()); // 조합의 크기 M 입력 nums = new int[N]; // 입력된 정수를 저장할 배열 생성 visited = new boolean[N]; // 방문 여부를 체크할 배열 생성 number = new int[M]; // 조합을 저장할 배열 생성 st = new StringTokenizer(br.readLine()); // 두 번째 줄의 입력 데이터 처리용 StringTokenizer 생성 for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 배열 nums에 정수 입력
• 정렬 및 조합 생성
  • 입력된 배열을 오름차순으로 정렬한 후, comb 함수를 호출하여 조합을 생성하고 결과를 출력한다.
• Arrays.sort(nums); // 입력된 배열을 오름차순으로 정렬 comb(0, 0); // 조합 생성 함수 호출 System.out.println(sb); // 결과 출력

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

• 조합 생성
  • comb 함수는 재귀적으로 호출되며, M개의 숫자가 선택될 때까지 조합을 생성한다.
  • 오름차순을 유지하기 위해 이전에 선택된 숫자보다 큰 숫자만 선택한다.
• public static void comb(int idx, int start) { if (idx == M) { // 조합이 M개의 숫자로 채워졌을 때 for (int i : number) sb.append(i + " "); // 조합을 StringBuilder에 추가 sb.append("\n"); // 줄바꿈 } else { for (int i = start; i < N; i++) { if (idx == 0 || number[idx - 1] < nums[i]) { // 오름차순 조건을 만족하는지 확인 number[idx] = nums[i]; // 현재 인덱스에 숫자 추가 comb(idx + 1, i + 1); // 다음 인덱스와 시작 위치로 재귀 호출 } } } }

5. 전체 코드

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

public class BOJ15655 {
    static int N, M;
    static int[] nums;
    static int[] number;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

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

        N = Integer.parseInt(st.nextToken()); // 배열의 크기 N 입력
        M = Integer.parseInt(st.nextToken()); // 조합의 크기 M 입력
        nums = new int[N]; // 입력된 정수를 저장할 배열 생성
        visited = new boolean[N]; // 방문 여부를 체크할 배열 생성
        number = new int[M]; // 조합을 저장할 배열 생성

        st = new StringTokenizer(br.readLine()); // 두 번째 줄의 입력 데이터 처리용 StringTokenizer 생성
        for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 배열 nums에 정수 입력

        Arrays.sort(nums); // 입력된 배열을 오름차순으로 정렬
        comb(0, 0); // 조합 생성 함수 호출
        System.out.println(sb); // 결과 출력
    }

    public static void comb(int idx, int start) {
        if (idx == M) { // 조합이 M개의 숫자로 채워졌을 때
            for (int i : number) sb.append(i + " "); // 조합을 StringBuilder에 추가
            sb.append("\n"); // 줄바꿈
        }
        else {
            for (int i = start; i < N; i++) {
                if (idx == 0 || number[idx - 1] < nums[i]) { // 오름차순 조건을 만족하는지 확인
                    number[idx] = nums[i]; // 현재 인덱스에 숫자 추가
                    comb(idx + 1, i + 1); // 다음 인덱스와 시작 위치로 재귀 호출
                }
            }
        }
    }
}