[BOJ/Java] N과 M (5) (15654)

N과 M (5) (15654)

1. 문제 분석

문제 개요

• N개의 자연수 중에서 M개를 고른 수열을 모두 출력하는 문제이다.
• 각 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입력 형식

• 첫 번째 줄에 자연수 N과 M이 주어진다.
• 두 번째 줄에 N개의 자연수가 주어진다.

출력 형식

• M개의 수로 이루어진 수열을 사전 순으로 출력한다.

2. 알고리즘 종류

• 이 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결한다. 백트래킹을 통해 모든 가능한 수열을 생성하고, 조건에 맞는 수열을 출력한다.

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

1. 입력 처리 및 초기화

• 입력을 받아 N개의 수를 저장하고, 수열을 생성하기 위한 배열과 방문 여부를 체크하는 배열을 초기화한다.

2. 백트래킹을 통한 수열 생성

• 백트래킹 기법을 사용하여 재귀적으로 모든 가능한 수열을 생성한다.

3. 결과 출력

• 생성된 모든 수열을 StringBuilder를 사용해 출력 형식에 맞게 출력한다.

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]; // N개의 수를 저장할 배열 생성 visited = new boolean[N]; // 방문 여부를 체크할 배열 생성 number = new int[M]; // M개의 수열을 저장할 배열 생성 st = new StringTokenizer(br.readLine(), " "); // 두 번째 줄의 입력을 공백을 기준으로 분리 for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 입력받은 N개의 수를 배열에 저장 Arrays.sort(nums); // nums 배열을 오름차순으로 정렬 perm(0); // 백트래킹을 이용해 수열 생성 System.out.println(sb); // 결과 출력

(2) 순열 함수(perm)

• 백트래킹을 통한 수열 생성
  • perm 함수를 통해 백트래킹을 사용하여 모든 가능한 수열을 생성한다.
  • 현재 인덱스가 M에 도달하면 수열을 결과 문자열에 추가하고, 그렇지 않으면 다음 수를 선택한다.
• public static void perm(int idx) { // idx번째 수열을 생성하는 함수 if (idx == M) { // M개의 수를 모두 선택한 경우 for (int i : number) sb.append(i + " "); // 현재까지 선택한 수열을 결과 문자열에 추가 sb.append("\n"); // 줄바꿈 추가 } else { // 아직 M개의 수를 선택하지 않은 경우 for (int i = 0; i < N; i++) { // 모든 수에 대해 반복 if (!visited[i]) { // 아직 방문하지 않은 경우 number[idx] = nums[i]; // 현재 수를 수열에 추가 visited[i] = true; // 현재 수를 방문했다고 표시 perm(idx + 1); // 다음 수 선택 visited[i] = false; // 현재 수를 선택에서 제외 } } } }

5. 전체 코드

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

public class BOJ15654 {
    static int N, M; // 자연수 N과 M
    static int[] nums; // 입력받은 N개의 수를 저장할 배열
    static int[] number; // 선택한 M개의 수를 저장할 배열
    static boolean[] visited; // 방문 여부를 체크할 배열
    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]; // N개의 수를 저장할 배열 생성
        visited = new boolean[N]; // 방문 여부를 체크할 배열 생성
        number = new int[M]; // M개의 수열을 저장할 배열 생성

        st = new StringTokenizer(br.readLine(), " "); // 두 번째 줄의 입력을 공백을 기준으로 분리
        for (int i = 0; i < N; i++) nums[i] = Integer.parseInt(st.nextToken()); // 입력받은 N개의 수를 배열에 저장

        Arrays.sort(nums); // nums 배열을 오름차순으로 정렬
        perm(0); // 백트래킹을 이용해 수열 생성
        System.out.println(sb); // 결과 출력
    }
    public static void perm(int idx) { // idx번째 수열을 생성하는 함수
        if (idx == M) { // M개의 수를 모두 선택한 경우
            for (int i : number) sb.append(i + " "); // 현재까지 선택한 수열을 결과 문자열에 추가
            sb.append("\n"); // 줄바꿈 추가
        }
        else { // 아직 M개의 수를 선택하지 않은 경우
            for (int i = 0; i < N; i++) { // 모든 수에 대해 반복
                if (!visited[i]) { // 아직 방문하지 않은 경우
                    number[idx] = nums[i]; // 현재 수를 수열에 추가
                    visited[i] = true; // 현재 수를 방문했다고 표시
                    perm(idx + 1); // 다음 수 선택
                    visited[i] = false; // 현재 수를 선택에서 제외
                }
            }
        }
    }
}