[백준][Java] 6603번 : 로또

[문제 링크]

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

---

문제 설명

하나의 테스트 케이스에 k와 k개의 수로 이루어진 집합 S를 입력받는다.

집합 S에서 6개의 수를 고르는 방법을 사전순으로 모두 출력한다. 6개의 수를 고를 때, 숫자의 순서는 상관없다.

 

 

 

 

 

 

문제 풀이

• 백트래킹 풀이
• cnt = 고른 숫자의 개수, start = 반복문 시작 인덱스
• start ~ k 를 돌면서 숫자를 하나씩 선택한 후, 재귀호출 한다.
• 재귀 호출을 할 때는 현재 선택한 수의 바로 다음 위치부터 탐색을 시작하도록 start = i + 1 로 설정한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

    public static int k;
    public static int[] numbers = new int[13];
    public static int[] result = new int[6];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());

            if (k == 0) {
                break;
            }
            else {
                for (int i = 0; i < k; i++) {
                    numbers[i] = Integer.parseInt(st.nextToken());
                }
               selectNumbers(0, 0);
                System.out.println();
            }
        }
    }

    public static void selectNumbers(int cnt, int start) {
        //종료 조건
        if (cnt == 6) {
            for (int i : result) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i < k; i++) {
            result[cnt] = numbers[i];
            selectNumbers(cnt + 1, i + 1);
        }
    }
}

 

 

 

실패한  풀이(나의 풀이)

반복문을 사용해서 cnt ~ k 까지의 인덱스를 돌고, visited 배열을 사용해서 선택한 숫자는 방문 처리를 한다.

하지만 이렇게 하면 '1 2 3 4 6 7'과 '1 2 3 4 7 6' 은 같은 경우인데 모두 선택되어서 출력된다.

다시 생각해보면 반복문에서 cnt부터 시작하는 것도 이상하다..

public static void selectNumbers(int k, int cnt) {
    if (cnt == 6) {
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println();
        return;
    }

    for (int i = cnt; i < k; i++) {
        if (!visited[i]) {
            visited[i] = true;
            result[cnt] = numbers[i];
            selectNumbers(k,cnt + 1);
            visited[i] = false;
        }
    }
}