[백준] 6603. 로또 (자바 JAVA)
문제
독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.
로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.
예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지다.
([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.
예제 입력 1
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0
예제 출력 1
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
JAVA 풀이
이 문제는 순열에 관한 문제이고, 순서가 정해져 있고 중복이 안되는 순열을 만든다. 그리고 중복은 제외하므로 다음 Level(L)에서 이전의 수를 고려하지 않도록 for문의 초기값을 1씩 증가시키도록 solution 인자에 값을 넣어서 재귀를 하는 방식으로 구현한다. 재귀가 끝날 때마다 list의 마지막 원소가 삭제되도록 해서 다음에 새로운 재귀가 시작될 때 새로운 원소가 추가되게 한다. 그리고 L이 6이 되었을 때 list를 출력하도록 하면 된다.
import java.io.*;
import java.util.*;
public class Main {
static int k;
static ArrayList<Integer> list;
static int[] S;
public void solution(int start, int L) {
if (L == 6) {
for(int num: list) {
System.out.print(num + " ");
}
System.out.println();
return;
} else {
for (int i = start; i < k; i++) {
list.add(S[i]);
solution(i + 1, L + 1);
list.remove(list.size() - 1);
}
}
}
public static void main(String[] args) throws IOException {
Main main = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
k = Integer.parseInt(st.nextToken());
if (k == 0) {
break;
}
S = new int[k];
for (int i = 0; i < k; i++) {
S[i] = Integer.parseInt(st.nextToken());
}
list = new ArrayList<>();
main.solution(0, 0);
System.out.println();
}
}
}처음에 했던 풀이는 solution() 메소드에서 if-else문의 for문에서 if문으로 원소 방문 여부를 체크해주도록 했다. 하지만 재귀적으로 호출한 다음에는 start가 i + 1이라서 i번째를 다시 볼 일 자체가 없으니 굳이 방문 체크하지 않아도 되어서 visited 변수는 필요가 없다. 없어도 정답인 데다가 불필요한 코드는 과감히 없애는게 낫다.
public void solution(int start, int L) {
if (L == 6) {
for(int num: list) {
System.out.print(num + " ");
}
System.out.println();
return;
} else {
for (int i = start; i < k; i++) {
if (!visited[i]) {
visited[i] = true;
list.add(S[i]);
solution(i + 1, L + 1);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}