[BOJ/Java] N과 M (10) (15664)

N과 M (10) (15664)

1. 문제 분석

문제 개요

• 주어진 N개의 숫자 중에서 M개의 숫자를 중복 없이 선택하여 사전 순서대로 나열하는 모든 경우를 출력하는 문제이다. 다만, 선택된 숫자들은 반드시 오름차순으로 나열되어야 하며, 입력된 숫자들 중에서 동일한 숫자가 여러 번 존재할 수 있다.

입력 형식

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

출력 형식

• M개의 숫자를 중복 없이 선택하여 오름차순으로 나열한 모든 경우를 사전 순서대로 출력한다. 각 수열은 한 줄에 하나씩 출력된다.

2. 알고리즘 종류

• 이 문제는 조합을 사용하여 가능한 모든 경우를 생성하는 문제이다. 입력된 숫자들 중에서 M개의 숫자를 선택하여 중복되지 않도록 하며, 선택된 숫자들은 오름차순이어야 한다.

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

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

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

2. 조합 생성

• 재귀 함수를 사용하여 중복되지 않는 모든 조합을 생성하고, 결과를 Set에 저장하여 중복된 수열이 포함되지 않도록 한다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리

    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]; // 입력된 숫자를 저장할 배열 생성
    visited = new boolean[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); // 입력된 숫자를 오름차순으로 정렬

  • BufferedReader와 StringTokenizer를 사용하여 입력을 처리하고, 숫자 배열을 정렬하여 조합 생성을 준비한다.

• 조합 생성 호출 및 결과 출력

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

  • comb 함수를 호출하여 모든 가능한 조합을 생성하고, Set에 저장된 결과를 출력한다.

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

• 중복 없는 조합 생성

    public static void comb(int idx, int start) {
        if (idx == M) {
            StringBuilder sb = new StringBuilder();
            for (int i : numbers) sb.append(i + " "); // 현재 조합을 결과에 추가
            answer.add(sb.toString()); // Set에 추가하여 중복 방지
        }
        else {
            for (int i = start; i < N; i++) {
                if (visited[i]) continue; // 이미 방문한 숫자는 건너뛰기
                visited[i] = true; // 현재 숫자를 방문 처리
                numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장
                comb(idx + 1, i + 1); // 다음 인덱스로 재귀 호출, 선택 시작 지점 갱신
                visited[i] = false; // 백트래킹: 방문 표시 해제
            }
        }
    }

  • 현재 인덱스가 M에 도달하면, 현재 조합을 StringBuilder로 생성하고 Set에 추가하여 중복된 수열이 포함되지 않도록 한다.
  • 그렇지 않으면, 배열 nums의 숫자들을 순서대로 선택하여 조합을 생성하고, 방문 여부를 체크하면서 다음 인덱스로 재귀 호출하여 모든 가능한 중복 없는 조합을 탐색한다.
  • 재귀 호출 시 i + 1을 전달하여 오름차순 순서를 유지하도록 한다.

5. 전체 코드

import java.io.*;
import java.util.*;
 
public class BOJ15664 {
    static int N, M;
    static int[] nums, numbers;
    static boolean[] visited;
    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]; // 입력된 숫자를 저장할 배열 생성
        visited = new boolean[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, 0); // 조합 생성 함수 호출
        answer.forEach(System.out::println); // 결과 출력
    }
 
    public static void comb(int idx, int start) {
        if (idx == M) {
            StringBuilder sb = new StringBuilder();
            for (int i : numbers) sb.append(i + " "); // 현재 조합을 결과에 추가
            answer.add(sb.toString()); // Set에 추가하여 중복 방지
        }
        else {
            for (int i = start; i < N; i++) {
                if (visited[i]) continue; // 이미 방문한 숫자는 건너뛰기
                visited[i] = true; // 현재 숫자를 방문 처리
                numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장
                comb(idx + 1, i + 1); // 다음 인덱스로 재귀 호출, 선택 시작 지점 갱신
                visited[i] = false; // 백트래킹: 방문 표시 해제
            }
        }
    }
}