[BaekJoon] 6603번 로또 (Java) 문제 풀이 [Sliver 2]

문제

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

6603번: 로또

 

어떻게 풀 것인가?

오랜만에 알고리즘 포스팅을 하는 것 같다.

 

코테 실패 이후 다시금 알고리즘 공부를 빡세게 해야할 것 같다.

 

이번에는 로또문제이다. 다만 문제를 읽어보자. 

 

1 ~ 49개의 숫자중에 K개의 수를 뽑아서 이중에서 또 6개의 숫자를 골라야한다.

 

즉, 조합 문제이다.

 

이 문제의 경우 백트레킹이나 재귀를 이용한 조합 알고리즘을 이용한다면 쉽게 풀 수 있다.

    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

 

나는 알고리즘을 공부할 때는 가끔 암기도 적절하게 해야한다고 생각한다. 물론 이해를 기반으로 해야한다.

 

풀면서 놓쳤던점

입출력 방식에서 생각보다 애를 먹었다.

 

이 문제를 통해 얻어갈 것

조합 - 백트래킹

 

내 코드 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Objects;

// 백준알고리즘 6603번 로또
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String str = br.readLine();
            if (Objects.equals(str, "0")) break;
            String[] temp = str.split(" ");
            int n = Integer.parseInt(temp[0]);
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(temp[i + 1]);
            }
            Arrays.sort(arr);
            boolean[] visited = new boolean[n];
            combination(arr, visited, 0, n, 6);
            System.out.println();
        }
    }

    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

 

참고

https://bcp0109.tistory.com/15

조합 Combination (Java)