[BOJ/Java] N과 M (11) (15665)

N과 M (11) (15665)

1. 문제 분석

문제 개요

• 주어진 N개의 숫자 중에서 중복을 허용하여 M개의 숫자를 선택해 사전 순서대로 나열하는 모든 경우를 출력하는 문제이다.
• 같은 수를 여러 번 선택할 수 있으며, 선택한 숫자들이 오름차순일 필요는 없다. 중복된 수열은 제거해야 한다.

입력 형식

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

출력 형식

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

2. 알고리즘 종류

• 이 문제는 중복 순열 문제이다. 입력된 숫자들로부터 M개의 숫자를 중복을 허용하여 선택하고, 생성된 수열을 Set에 저장하여 중복된 수열이 포함되지 않도록 한다.

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

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

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

2. 중복 순열 생성

• 재귀 함수를 사용하여 중복을 허용하여 M개의 숫자를 선택하는 모든 경우의 수를 생성하고, 결과를 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]; // 입력된 숫자를 저장할 배열 생성
    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를 사용하여 입력을 처리하고, 숫자 배열을 정렬하여 중복 순열 생성을 준비한다.

• 중복 순열 생성 호출 및 결과 출력

    perm(0); // 중복 순열 생성 함수 호출
    answer.forEach(System.out::println); // 결과 출력

  • perm 함수를 호출하여 모든 가능한 중복 순열을 생성하고, Set에 저장된 결과를 출력한다.

(2) 중복 순열 생성 함수 (perm)

• 중복을 허용하여 M개의 숫자를 선택하는 경우 생성

    public static void perm(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++) {
                numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장
                perm(idx + 1); // 다음 인덱스로 재귀 호출
            }
        }
    }

  • 현재 인덱스가 M에 도달하면, 현재 순열을 StringBuilder로 생성하고 Set에 추가하여 중복된 수열이 포함되지 않도록 한다.
  • 그렇지 않으면, 배열 nums의 숫자들을 순서대로 선택하여 중복을 허용한 모든 순열을 생성하고, 재귀 호출을 통해 모든 가능한 경우를 탐색한다.

5. 전체 코드

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

public class BOJ15665 {
    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); // 입력된 숫자를 오름차순으로 정렬

        perm(0); // 중복 순열 생성 함수 호출
        answer.forEach(System.out::println); // 결과 출력
    }

    public static void perm(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++) {
                numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장
                perm(idx + 1); // 다음 인덱스로 재귀 호출
            }
        }
    }
}