백준 6603 - 로또 / Java

1. 문제

6603번: 로또

 

2. 알고리즘

1. k개의 수 중에서 6개를 조합하는 문제이다. 경우의 수는 kC6.

2. 재귀로 완전탐색을 실시하여 모든 조합을 찾은 후 출력한다.

3. 재귀의 return조건은 6개를 조합해야하므로 detph==6.

 

3. 코드

/**
 * 2020.07.28
 * 백준 6603 : 로또
 * DevHyeonseong
 */
import java.util.*;
public class BOJ6603 {
    public static int[] lotto;
    public static int[] answer;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String input = scan.nextLine();
        while(!input.equals("0")){
            String[] temp = input.split(" ");
            lotto = new int[temp.length-1];
            answer = new int[temp.length-1];

            int k = Integer.parseInt(temp[0]);

            for(int i=1;i<temp.length;i++){
                lotto[i-1] = Integer.parseInt(temp[i]);
            }
            dfs(0,0, k);
            System.out.println();

            input = scan.nextLine();
        }
    }

    public static void dfs(int idx, int depth,int k){
        if(depth==6){ // 6개의 순열이 만들어지면 출력후 return
            StringBuilder stringBuilder = new StringBuilder();
            for(int i=0;i<answer.length;i++){ // 자바의 System 호출을 여러번 하는것은 효율이 좋지 않으므로 한꺼번에 출력한다.
                if(answer[i]==0){
                    break;
                }
                stringBuilder.append(answer[i]+" ");
            }
            System.out.println(stringBuilder.toString().trim()); 
            return;
        }
        for(int i=idx;i<k;i++){
            answer[depth] = lotto[i];
            dfs(i+1,depth+1,k);
        }
    }
}

 

 

끝.