DFS 백준 알고리즘 자바 15649 ‘N과 M (1)’ 문제풀이

Problem

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. (1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열)열열)

Input 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

Output 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

Solution

문제를 풀고 나서 맞춘 사람 풀이를 봤는데 무려 메모리를 나보다 반이나 덜 쓰고 속도도 몇 배나 빨랐다. 그래서 여러 차례 수정을 했지만 속도는 격차를 많이 줄였지만 메모리는 많이 따라잡지 못 했다.ㅠㅠ

• 순열 문제라서 dfs로 풀었다.
• 처음에는 string builder를 쓰지 않고, d == m일 때 for문을 돌려 arr 배열을 출력했다. string builder를 사용해서 나중에 한 번에 출력하면 속도를 무려 4~5배나 줄일 수 있다.
• 입력 받는 값이 2개 뿐이라 scanner를 사용했는데, bufferedReader를 쓰고 string tokenizer까지 사용하면 메모리 크기를 5분의 1정도 줄일 수 있다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	static int[] arr;
	static boolean[] visit;
	static StringBuilder sb = new StringBuilder();
	
	private static void dfs(int n, int m, int d) {
		if(d == m) {
			for(int a : arr) sb.append(a + " ");
			sb.append("\n");
			return;
		}
		
		for(int i = 1; i <= n; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[d] = i;
				dfs(n, m, d+1);
				visit[i] = false;
			}
		}
		return;
	}
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
		arr = new int[m]; visit = new boolean[n+1];
		
		dfs(n, m, 0);
		System.out.print(sb);
	}
}