백준 6603 로또 Java

->2019. 6. 18 수정

여러 가지의 방법으로 풀 수 있는 문제인 로또 문제이다.

우선 순열을 사용한 완전 탐색으로 푸는 방법을 정리하고

백트래킹을 사용한 완전 탐색으로 푸는 방법을 정리한다.

 

먼저 순열은 중복된 수가 있어도 정상적으로 작동한다.

https://dundung.tistory.com/58

백준 10972 이전 순열 & 10973 다음 순열 Java

이 글에서 알아본 nextPermutation(다음 순열)을 구하는 메소드는 중복된 수가 있는 순열이라도 

잘 처리하도록 만들어진 메소드 이다.

만약 0 0 1 1이라는 순열이 있으면

다음 순열은

0 1 0 1

다음은

0 1 1 0

이런 식으로 중복된 수도 잘 처리해서 다음 순열을 구하게 된다.

중복된 수가 있으므로 n이 4개일 때 

N! 만큼의 순열이 나오지 않는다.

N! / 어떤 수의 중복된 수의 개수! * 어떤 수의 중복된 수의 개수! *...

만큼의 순열의 개수가 나오게 된다.

위의 0 0 1 1의 경우엔

4! = 24개의 순열이 나오는 것이 아니

0이 2개 중복되고 1이 2개 중복되므로

4! / 2! * 2! -> 24 / 2 * 2 -> 6개의 순열이 나오는 것이다.

 

이러한 성질을 이용해서 로또를 구하면 된다.

임의의 배열을 만들어서

N - 6만큼은 0을 넣어주고

6개만큼 1을 넣어준다.

그리고 이 배열의 다음 순열을 계속 구하며

d[i]가 1일 때 a[i]를 다른 배열에 넣어주고

완성된 배열을 정답 배열에 넣어주면 된다.

 

자세히 말하면

입력으로 n이 7 로또번호 배열 a= { 1 2 3 4 5 6 7 } 주어졌을 때

n-6 = 1

1개의 0을 먼저 임의의 배열 d에 넣어준다.

그리고 6개만큼의 1을 d에 또 넣어준다.

그렇다면 d 배열은 현재 0 1 1 1 1 1 1 일 것이다.

그리고 입력받은 a배열에서 d의 인덱스가 1인 경우에만

정답 배열에 넣어준다.

처음 d배열이 0 1 1 1 1 1 1 이므로

d[0] = 0이기 때문에 넣지 않고

d[1] ~ d[6]은 1이기 때문에

a[1] ~ a[6]을 정답 배열에 넣어준다.

정답 배열엔 2 3 4 5 6 7 이 들어가게 된다.

그리고 d의 다음 순열을 구하면

1 0 1 1 1 1 1이 될 것이고

마찬가지로

1 3 4 5 6 7을 정답 배열에 넣는다.

이런 식으로 로또번호가 가능한 모든 경우를 정답 배열에 넣고

정답 배열을 정렬한 후 출력하면 된다.

 

순열을 넣어둘 정답 배열을

List<List<Integer>> answer = new ArrayList<>(); 

이런 식으로 선언했다.

List<Integer>로 이루어진 List인 것이다.

이 배열을 정렬할 때

배열로 이루어진 list이기 때문에

Collections.sort로는 불가능하다.

 

answer.sort(x, y)에서 람다식으로

Comparator인터페이스의 compareTo메소드를 재정의 하여

정렬하였다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Q6603 {
    public static void swap(List<Integer> a, int i, int j) {
        int temp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }
    public static boolean nextPermutation(List<Integer> a) { //다음 순열 구하기
        int i = a.size()-1;
        while(i > 0 && a.get(i) <= a.get(i-1))
            i--;
        if(i < 1)
            return false;
        int j = a.size()-1;
        while(a.get(j) <= a.get(i-1))
            j--;
        swap (a, i-1, j);
        j = a.size()-1;
        while(i < j) {
            swap(a, i , j);
            i++;
            j--;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scan  = new Scanner(System.in);
        while (true) {
            int n = scan.nextInt();
            if (n == 0) {
                break;
            }
            int []a = new int[n];
            for (int i=0; i<n; i++) {
                a[i] = scan.nextInt();
            }
            List<Integer> d = new ArrayList<>(); //순열 배열
            for (int i=0; i<n-6; i++) {
                d.add(0);
            }
            for (int i=0; i<6; i++) {
                d.add(1);
            }
            List<List<Integer>> ans = new ArrayList<>(); //정답 배열
            do {
                List<Integer> current = new ArrayList<>(); //임시 배열
                for (int i=0; i<n; i++) {
                    if (d.get(i) == 1) {
                        current.add(a[i]);
                    }
                }
                ans.add(current);
            } while (nextPermutation(d));
            
            ans.sort((x, y) -> { //List<List<Integer> 를 람다식으로 compareTo를 재정의 후 정렬
                int r = 0;
                for(int i=0; i<ans.size(); i++) {
                    r = x.get(i)- y.get(i);
                    if(r!=0)
                        break;
                }
                return r;
            });
                
            for(List<Integer> k : ans) { //출력
                for (int i=0; i<k.size(); i++) {
                    System.out.print(k.get(i)+" ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}

 

백트래킹을 사용하는 풀잇법은 코드가 훨씬 간단하다.

수가 오름차순으로 정렬되어있기 때문에 방문했는지 안 했는지 체크하는 배열은 필요 없다.

암호 만들기 문제에서처럼 수를 사용하는 경우, 사용하지 않는 경우로 나누어 백트래킹을 해주면 된다.

중요한 점은 a배열의 인덱스와 몇 번들 어갔는지 세어줄 cnt변수가 메소드의 파라미터로 들어간다는 점이다.

사용하는 경우에서 이미 로또 번호를 저장할 list에 수가 들어가 있기 때문에

list.remove(list.size()-1)을 해준 뒤 수를 사용하지 않는 경우를 재귀 호출한다. 

 

사용하는 경우와 사용하지 않는 경우를 이용한 백트래킹은 아마도

오름차순으로 정렬되어있어서 순서대로 탐색할 때 사용하는 듯하다.

일반 백트래킹처럼 구현도 해봤는데

순서가 뒤죽박죽 되면서 N!만큼 모든 번호를 출력하는 모습을 볼 수 있었다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q6603_ver2 {
    public static List<Integer> list = new ArrayList<>(); 
 
    public static void go(int [] a, int index, int cnt) {
        if(cnt==6) { //출력
            for(int v : list)
                System.out.print(v+" ");
            System.out.println();
            return;
        }
        if(index >= a.length) return;
        
        list.add(a[index]);
        go(a, index+1, cnt+1); //사용하는 경우
        list.remove(list.size()-1);
        go(a, index+1, cnt); //사용하지 않는 경우
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(true) {
            int n = scan.nextInt();
            if(n == 0) break;
            int [] a = new int[n];
            boolean [] b = new boolean[n];
            for(int i=0; i<n; i++) {
                a[i] = scan.nextInt();
            }
            go(a, 0, 0);
            System.out.println();
            list.clear();
        }
    }
 
}