백준 15651번: N과 M (3)

중복순열에 대한 문제이다.

 

(1) StringBuilder 사용

import java.util.Scanner;

public class Main {

	public static int N , M;
	public static int[] ans;
    public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args)  {	
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt(); //1~N까지의 숫자
		M = sc.nextInt(); //뽑을 숫자 갯수
		
		ans = new int[M];
		dfs(1,0); //숫자 1부터 N까지 돌것 , idx는 0
		System.out.println(sb);
	}
	
	public static void dfs(int num , int idx) {
		
		//종료조건 
		//M만큼 뽑았는가?
		if(idx==M) {
			for (int i = 0; i < ans.length; i++) {
				sb.append(ans[i]+" ");
			}
            sb.append("\n");
			return;
		}
		
		for (int i = 1; i <=N; i++) {
			
			ans[idx]=i;
			dfs(i,idx+1);

		}
	}

}

(2) 시간초과 난 코드

String과 System.out.println를 쓴 것이 원인.

System.out.println이 굉장히 속도를 저하시킨다고 한다. 그래서 스트링빌더 혹은 스트링버퍼를 사용해서 문자열을 계속 연산해주고 마지막에 한번만 출력한다.

 

또한 Scanner도 속도를 저하시키는데, 이를 개선하기 위해서 버퍼리더를 사용한다.

import java.util.Scanner;

public class Main {

	public static int N , M;
	public static int[] ans;
	public static void main(String[] args)  {	
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt(); //1~N까지의 숫자
		M = sc.nextInt(); //뽑을 숫자 갯수
		
		ans = new int[M];
		dfs(1,0); //숫자 1부터 N까지 돌것 , idx는 0

	}
	
	public static void dfs(int num , int idx) {
		
		//종료조건 
		//M만큼 뽑았는가?
		if(idx==M) {
			for (int i = 0; i < ans.length; i++) {
				System.out.print(ans[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for (int i = 1; i <=N; i++) {
			
			ans[idx]=i;
			dfs(i,idx+1);

		}
	}

}