[BOJ/Java] N과 M (9) (15663)

N과 M (9) (15663)

1. 문제 분석

문제 개요

• 주어진 N개의 숫자 중에서 M개의 숫자를 중복 없이 나열하는 모든 경우를 출력하는 문제이다. 다만, 입력된 숫자들이 중복될 수 있기 때문에, 결과에는 중복된 수열이 포함되지 않도록 해야 한다.

입력 형식

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

출력 형식

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

2. 알고리즘 종류

• 이 문제는 순열을 사용하여 가능한 모든 경우를 생성하는 문제이다. 입력된 숫자들 중에서 M개의 숫자를 선택하여 중복되지 않도록 나열하며, 중복된 결과는 출력하지 않는다.

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

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

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

2. 순열 생성

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

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]; // 입력된 숫자를 저장할 배열 생성 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); // 입력된 숫자를 오름차순으로 정렬
• 순열 생성 호출 및 결과 출력
  • perm 함수를 호출하여 모든 가능한 순열을 생성하고, Set에 저장된 결과를 출력한다.
• perm(0); // 순열 생성 함수 호출 answer.forEach(System.out::println); // 결과 출력

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

• 중복 없는 순열 생성
  • 현재 인덱스가 M에 도달하면, 현재 순열을 StringBuilder로 생성하고 Set에 추가하여 중복된 수열이 포함되지 않도록 한다.
  • 그렇지 않으면, 배열 nums의 모든 숫자를 현재 인덱스에 배치하고, 방문 여부를 체크하면서 다음 인덱스로 재귀 호출하여 모든 가능한 중복 없는 순열을 생성한다.
• public static void perm(int idx) { if (idx == M) { StringBuilder sb = new StringBuilder(); for (int i : numbers) sb.append(i + " "); // 현재 순열을 결과에 추가 answer.add(sb.toString()); // Set에 추가하여 중복 방지 } else { for (int i = 0; i < N; i++) { if (visited[i]) continue; // 이미 방문한 숫자는 건너뛰기 visited[i] = true; // 현재 숫자를 방문 처리 numbers[idx] = nums[i]; // 현재 인덱스에 숫자 저장 perm(idx + 1); // 다음 인덱스로 재귀 호출 visited[i] = false; // 백트래킹: 방문 표시 해제 } } }

5. 전체 코드

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

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

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

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