백준(BOJ) 6603 : 로또 (실버3) / 자바(Java) 풀이

문제

https://www.acmicpc.net/problem/6603

3줄 요약

1. 이 코드는 재귀 함수 recursion을 활용하여 주어진 집합 S에서 크기가 6인 조합을 사전순으로 생성하고 출력하는 문제를 해결합니다.
2. 재귀 함수 recursion은 현재 선택한 숫자의 개수(depth)와 인덱스(idx)를 매개변수로 받아, 조합을 생성합니다.
   • 선택한 숫자의 개수가 6이 되면 선택한 숫자를 출력하고 종료합니다.
   • 현재 인덱스의 숫자를 선택하는 경우와 선택하지 않는 경우로 나누어 재귀 호출을 수행하며, 이를 통해 모든 가능한 조합을 탐색합니다.
   • 조합을 사전순으로 생성하기 위해, 현재 인덱스(idx)를 조정합니다.
     • 현재 인덱스의 숫자를 선택하는 경우, 다음 재귀 호출에서는 idx + 1을 전달하여 다음 인덱스부터 조합을 생성합니다.
     • 현재 인덱스의 숫자를 선택하지 않는 경우에도 idx + 1을 전달하여 다음 인덱스부터 조합을 생성합니다.
   • 이렇게 인덱스를 조정함으로써, 선택한 숫자들의 순서가 항상 사전순으로 유지됩니다.
3. 주어진 입력에 대해 각 테스트 케이스마다 재귀 함수를 호출하여 조합을 생성하고 출력합니다. 입력이 "0"이 될 때까지 반복하며, 각 테스트 케이스 사이에 빈 줄을 출력합니다.

코드

// package boj6603;

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

public class Main {
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src/input.txt")); // 입력 파일에서 데이터 읽기 (테스트용)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String input;
        while ((input = br.readLine()) != null && !input.equals("0")) { // 입력이 "0"이 아닐 때까지 반복
            StringTokenizer st = new StringTokenizer(input);
            int k = Integer.parseInt(st.nextToken()); // 집합 S의 크기 k 입력받기
            int[] S = new int[k]; // 크기가 k인 집합 S 배열 생성
            
            for (int i = 0; i < k; i++) {
                S[i] = Integer.parseInt(st.nextToken()); // 집합 S의 원소 입력받기
            }
            
            recursion(S, 0, 0, new int[6], bw); // 재귀 함수 호출하여 조합 생성
            bw.write("\n"); // 각 테스트 케이스 사이에 빈 줄 출력
        }
        
        br.close();
        bw.flush();
        bw.close();
    }
    
    // 재귀 함수를 사용하여 조합 생성
    public static void recursion(int[] S, int depth, int idx, int[] tmp, BufferedWriter bw) throws IOException {
        if (depth == 6) { // 선택한 숫자의 개수가 6이 되면
            for (int i = 0; i < 6; i++) {
                bw.write(tmp[i] + " "); // 선택한 숫자 출력
            }
            bw.newLine(); // 줄 바꿈
            return;
        }
        
        if (idx >= S.length) { // 인덱스가 집합 S의 크기 이상이면 종료
            return;
        }
        
        tmp[depth] = S[idx]; // 현재 인덱스의 숫자 선택
        recursion(S, depth + 1, idx + 1, tmp, bw); // 다음 숫자 선택을 위해 재귀 호출
        recursion(S, depth, idx + 1, tmp, bw); // 현재 숫자를 선택하지 않고 다음 인덱스로 이동
    }
}