[백준 JAVA] 6603 로또

6603 로또

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

문제설명

각 테스트 케이스는 첫 번째 수 k와 그 뒤에 k개의 오름차순으로 정렬된 숫자로 구성된다.

각 테스트 케이스로 k개의 숫자에서 6개의 숫자를 선택하는 모든 조합을 생성해야 한다.

접근방식

O(n)  시간복잡도

• 팰린드롬 검사 함수의 호출 과정:
  • 함수 recursion(s, l, r)는 문자열의 양 끝에서부터 비교를 시작하여 문자열의 길이만큼 재귀적으로 호출된다.
  • 이 함수는 문자열의 길이에 비례하여 호출된다.
  • 재귀 호출은 문자열의 길이에 따라 최대 n/2번 호출될 수 있다.
  • 각 호출은 상수 시간 O(1)의 작업을 수행하므로,
  • 재귀 호출 자체의 시간복잡도는 O(n)이다.

문제 조건 분석 과정

 

• 조합을 생성하기 위해 깊이 우선 탐색(DFS)을 사용한다.
• DFS는 num 리스트에서 6개의 숫자를 선택하는 모든 조합을 생성한다.

수학적 접근

• num.size()를 n이라고 할 때, 조합의 수는 C(n, 6)이다.
• C(n, 6)는 n개의 요소에서 6개를 선택하는 조합의 수를 의미하며
• 수식은 이렇다

• 

  수식

전체코드

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

public class Main {
    // 깊이 우선 탐색(DFS) 방식으로 조합을 생성하는 메서드
    private static void lottery(List<Integer> num, int start, List<Integer> C, List<List<Integer>> result) {
        // 조합의 크기가 6인 경우, 현재 조합을 결과 리스트에 추가
        if (C.size() == 6) {
            result.add(new ArrayList<>(C));
            return;
        }

        // start 인덱스부터 끝까지 탐색
        for (int i = start; i < num.size(); i++) {
            C.add(num.get(i)); // 현재 숫자를 조합에 추가
            lottery(num, i + 1, C, result); // 재귀 호출로 다음 숫자 조합 생성
            C.remove(C.size() - 1); // 백트래킹: 마지막 추가된 숫자를 제거하여 다른 조합 시도
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        boolean firstCase = true; // 첫 번째 테스트 케이스 여부를 체크하기 위한 변수

        while ((line = br.readLine()) != null) {
            // 입력된 문자열을 공백으로 분리하여 배열로 변환
            String[] parts = line.split(" ");
            int k = Integer.parseInt(parts[0]); // 첫 번째 숫자는 집합의 크기 k

            // k가 0인 경우 입력 종료
            if (k == 0) {
                break;
            }

            // 첫 번째 테스트 케이스가 아닌 경우 결과 사이에 빈 줄을 추가
            if (!firstCase) {
                System.out.println();
            }
            firstCase = false;

            // k개의 숫자를 리스트에 저장
            List<Integer> numbers = new ArrayList<>();
            for (int i = 1; i <= k; i++) {
                numbers.add(Integer.parseInt(parts[i]));
            }

            // 조합을 저장할 리스트
            List<List<Integer>> results = new ArrayList<>();
            // 깊이 우선 탐색을 호출하여 모든 조합을 생성
            lottery(numbers, 0, new ArrayList<>(), results);

            // 생성된 모든 조합을 출력
            for (List<Integer> C : results) {
                for (int i = 0; i < C.size(); i++) {
                    System.out.print(C.get(i));
                    if (i < C.size() - 1) {
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }
}