[백준] 6603 로또- Backtracking / Java

• 문제 링크

6603번: 로또

 

• 풀이 과정

while 문에서 입력의 한 라인을 StringTokenizer 로 받되, 첫 토큰이 0이 아닐 시에만 탐색을 수행한다.

첫 토큰이 곧 문제상 k값이며 int 배열 arr 와 boolean 배열 visit 의 크기를 k 로 생성하고 원소를 저장한다.

 

해당 배열을 재귀 함수의 깊이가 6일 때까지 호출하여 탐색하며,

인덱스의 방문 여부를 확인하는 방식으로 구한 각각의 순열을 StringBuilder 에 적절히 줄바꿈하여

하나의 테스트 케이스로써 저장 및 출력한다.

 

• 풀이 코드

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

public class Main {

	static int k;
	static int[] arr;
	static boolean[] visit;
	static StringBuilder sb;

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

		while (true) {
			st = new StringTokenizer(br.readLine());
			k = Integer.parseInt(st.nextToken());
			if (k != 0) {
				arr = new int[k];
				visit = new boolean[k];
				
				for (int i = 0; i < k; i++)
					arr[i] = Integer.parseInt(st.nextToken());

				sb = new StringBuilder();
				recur(0, 0);

				bw.write(sb + "\n");
			} else
				break;
		}

		bw.flush();
	}

	private static void recur(int start, int depth) {
		if (depth == 6) {
			for (int i = 0; i < k; i++) {
				if (visit[i])
					sb.append(arr[i] + " ");
			}
			sb.append("\n");
			return;
		}

		for (int i = start; i < k; i++) {
			visit[i] = true;
			recur(i + 1, depth + 1);
			visit[i] = false;
		}
	}

}