알고리즘 풀이 - 백준 6603(로또, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

 

2. 풀이

 

 숫자 1~49 중 6개에서 13개(K의 범위)가 주어지는데, 이 중 6개를 골라 오름차순의 순서대로 고르는 방법이다.

이 문제는 기본적으로 선택의 문제이므로 6개가 선택될 때까지 재귀 방식으로 해결하거나 혹은 순열을 이용하여 해결할 수 있다.

 

① 재귀로 해결하기

재귀 메소드를 구현하여, 현재 몇 개의 숫자가 선택되었는지, 선택된 숫자를 저장하여 6개가 모두 선택되면 그 내용을 출력하는 방식으로 해결할 수 있다.

 

② 순열로 해결하기

이것은 선택의 문제인데 이를 순서의 문제로 치환하는 방법을 사용하면 해결할 수 있다.

 

K개의 숫자가 주어질 때, 선택된 숫자는 1로, 선택되지 않은 숫자는 2로 치환하면 1은 6개이고 2는 K-6개이다.

이를 이용하여 1, 2의 숫자로만 치환된 배열을 순열로 순서를 구하면 전체 경우의 수를 사전 순으로 구할 수 있게 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 재귀로 해결하기

import java.io.*;

public class Main{
    static int k;
    static int[] nums;
    static int[] chosen;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        while(true){
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            
            // 0이 주어진 경우는 더 이상 테스트 케이스가 없는 경우이므로 빠져나간다.
            if(n == 0) break;
            
            // 주어진 숫자 저장
            k = n;
            nums = new int[n];
            chosen = new int[6];
            
            for(int i=1; i <= n; i++){
                nums[i-1] = Integer.parseInt(line[i]);
            }
            
            recursive(0, 0);
            
            // 다음 테스트 케이스 이전에 빈 칸을 출력
            sb.append("\n");
        }
        
        System.out.println(sb);
        br.close();
    }
    
    // 재귀로 해결하는 메소드
    private static void recursive(int depth, int idx) throws IOException{
        // 탈출 조건 정의
        if(depth == 6){
            for(int n : chosen){
                sb.append(String.valueOf(n)).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i=idx; i < k; i++){
            chosen[depth] = nums[i];
            recursive(depth+1, i+1);
        }
    }
}

※ 상단의 코드에서 BufferedWriter를 쓰지 않고 StringBuilder를 쓴 이유는 BufferedWriter 사용 시, 런타임 에러가 발생하기 때문입니다.(이유를 아시는 분은 댓글로 주시면 감사합니다. ㅠㅠ)

 

② 순열로 해결하기

import java.io.*;

public class Main{
    static int k;
    static int[] nums;
    static int[] perm;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        while(true){
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            
            // 0이 주어진 경우는 더 이상 테스트 케이스가 없는 경우이므로 빠져나간다.
            if(n == 0) break;
            
            // 주어진 숫자 저장
            k = n;
            nums = new int[n];
            perm = new int[n];
            
            int chosen = 0;
            for(int i=1; i <= n; i++){
                nums[i-1] = Integer.parseInt(line[i]);
                
                // 6개 제일 앞에서부터 선택 - 선택된 것은 1, 아닌 것은 2
                if(chosen < 6) {
                    perm[i-1] = 1;
                } else {
                    perm[i-1] = 2;
                }
                chosen++;
            }
            
            while(true){
                for(int i=0; i < n; i++){
                    if(perm[i] == 1){
                        bw.write(String.valueOf(nums[i]) + " ");
                    }                    
                }
                bw.write("\n");
                
                boolean isNext = getNext();
                if(!isNext) break;
            }
            bw.write("\n");
        }
        
        bw.flush();
        br.close();
    }
    
    // 다음 순열을 구하는 메소드
    private static boolean getNext(){
        int i = k-1;
        while(i > 0 && perm[i-1] >= perm[i]) i--;
        if(i <= 0) return false;
        
        int j = i-1;
        while(j < k-1 && perm[j+1] > perm[i-1]) j++;
        swap(i-1, j);
        
        j = k-1;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
        return true;
    }
    
    private static void swap(int i, int j){
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.