백준 15650번 15652번 N과 M(2) N과 M(4) 문제

조합을 구하는 것 같은 문제.. dfs 알고리즘을 사용하여 알고리즘을 참고했다. 그리고 string끼리 더하는 행위를 했는데 그것을 하게 되면 이클립스에선 됐는데 문제 정답 제출하니 시간 초과가 떠서 알아보니 StringBuilder라는 것을 사용하면 시간을 줄일 수 있다고 한다.

 

 StringBuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르고 상대적으로 부하가 적다고 한다.. 

 

package codetest;

import java.util.*;
import java.io.*;

public class Main {
	
	static int[] result;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Scanner 대신 사용 사용이유 앞 블로그에서 설명함
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		result=new int[m];
		dfs(n,m,1, 0);
		System.out.println(sb);
	}
		
		public static void dfs(int n,int m,int cnt, int depth) {
			 
			if (depth == m) {//배열의 개수가 m이되면 return
				for (int i = 0; i < m; i++) {
					sb.append(result[i]+" ");// 문자열을 더함
				}
				sb.append('\n');// 문자를 개행함
				return;
			}
	        
			for (int i = cnt; i <= n; i++) { //cnt보다 큰수만 dfs
				result[depth] = i;
				dfs(n,m,i + 1, depth + 1); // 재귀로 dfs cnt+1
			}
	}	
}

이 문제도 위와같은 알고리즘을 살짝 만 바꾸어 주면 문제 풀이가 가능 했다.. cnt+1했던걸 그냥 cnt만 보내줘서 반복하게 되면 된다

package codetest;

import java.util.*;
import java.io.*;

public class Main {
	
	static int[] result;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Scanner 대신 사용 사용이유 앞 블로그에서 설명함
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		result=new int[m];
		dfs(n,m,1, 0);
		System.out.println(sb);
	}
		
		public static void dfs(int n,int m,int cnt, int depth) {
			 
			if (depth == m) {//배열의 개수가 m이되면 return
				for (int i = 0; i < m; i++) {
					sb.append(result[i]+" ");// 문자열을 더함
				}
				sb.append('\n');// 문자를 개행함
				return;
			}
	        
			for (int i = cnt; i <= n; i++) { //cnt보다 큰수만 dfs
				result[depth] = i;
				dfs(n,m,i, depth + 1); // 재귀로 dfs
			}
	}	
}