Calm Dawn Studio

[JAVA] 백준 15651번 - N과 M (3)

1. BufferedWriter 을 통해 출력한 경우

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 BufferedReader br;
	static BufferedWriter bw;
	static int N;
	static int M;
	static int[] arr;

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

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[M];

		int depth = 0;

		solution(depth);

		bw.flush();
		bw.close();
	}

	private static void solution(int depth) throws IOException {

		if (depth == M) {
			for (int num : arr) {
				bw.write(num + " ");
			}
			bw.newLine();
			return;
		}

		for (int i = 1; i <= N; i++) {
			arr[depth] = i;
			solution(depth + 1);
		}
	}
}

2. StringBuilder를 사용해 출력한경우

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

public class Main {
	static BufferedReader br;
	static StringBuilder sb;
	static int N;
	static int M;
	static int[] arr;

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

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[M];

		int depth = 0;

		solution(depth);
		System.out.println(sb.toString());

	}

	private static void solution(int depth) {

		if (depth == M) {
			for (int num : arr) {
				sb.append(num).append(" ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 1; i <= N; i++) {
			arr[depth] = i;
			solution(depth + 1);
		}
	}
}

1, 2 모두 정답이지만 1번(BufferedWriter)방식이 메모리를 약 2배정도 더 사용함

정답을 맞춘 풀이방법

1. 기존에 풀어왔던 N과 M 방식과 유사하며, 모든 경우의 수를 출력함

2. 이전에 사용했던 수를 확인할 필요가 없으므로 isUsed[]과 같은 배열은 필요없음

3. depth == M, 수열의 길이가 M과 같다면 출력함