[백준,BOJ 15651] N과 M(3) (JAVA 구현)

-내 생각

  이번 문제 역시 이전의 N과 M문제들과 같은 맥락의 문제였다. 차이점은 이 문제에서는 순열 + 이미 선택한 숫자를 중복해서 선택할 수 있다는 점이다. 구현으로는 어렵지 않았다. 단순히 방문 배열을 사용하지만 않으면 됐다. 하지만 처음으로 구현 후 출력까지 확인 후 제출을 했는데 시간 초과가 나버렸다... 아직 시간 복잡도 등을 고려할 수준이 못되기 때문에 어디서 문제가 있는 것인지 찾을 수 없었는데, 검색하는 도중 자바의 경우에는 일반적인 입출력을 사용할 시 시간 초과가 날 수 있다는 글을 보고 바로 수정한 후 제출했더니 정답처리를 받을 수 있었다. 

 

-해법

  자바에서 일반적으로 우리가 사용하는 입출력 라이브러리는 Scanner를 이용한 입력방법과 System.out.print();를 이용한 출력방식을 많이 사용하는데, 이는 c++에서 사용하는 cin, cout이나 c에서 사용하는 printf();등과는 다르게 속도적인 측면에서 많이 느리다고 한다. 그래서 자바로 알고리즘 문제를 풀 경우에는 BufferedReader과 BufferedWriter을 사용해야 하는데 아무래도 Scanner나 sysout보다는 타이핑해야하는 양이 많아지기 때문에 귀찮아서 잘 안 쓰고 있었는데, 그 중요성을 이번 문제로 다시 한번 깨달았다.

 

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

public class Main {
	static int m,n;

	static int list[]; // 수열을 저장 할 배열
    //BufferedWriter 객체, static선언을 한 이유는 DFS메소드 내에서 출력을 하기 때문이다.
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
    
	static void dfs(int cnt) throws IOException { //DFS메소드, 
    		 //출력부가 있기 때문에 bw객체를 사용할 때에는 입출력 예외처리가 필수
		
		if(cnt == m) {
			for(int i=0;i<m;i++) {
				bw.write(String.valueOf(list[i])+" ");	//bw.write()를 이용한 출력		
				}
			bw.newLine(); // 개행
			return;
		}
		
		for(int i =1;i<=n;i++) { // 중복이 허용되므로 1부터 n까지 계속반복한다.
			//방문배열을 처리해주는 부분이 사라졌다.
			list[cnt]=i;		
			dfs(cnt+1);			
		}	
	}
	
	public static void main(String[] args) throws IOException {
    	//마찬가지로 main부에 입력 처리가 있으므로 입출력 예외처리가 필수
//		Scanner sc = new Scanner(System.in); //기존에 사용한 Scanner클래스
		
        //BufferedReader 객체 생성
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //공백을 기준으로 입력받기 때문에 공백 구분을 위해 StringTokenizer 객체를 함께 사용한다.
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		n = Integer.parseInt(st.nextToken()); // 공백을 구분으로 입력
		m = Integer.parseInt(st.nextToken()); // 공백을 구분으로 입력
		
		
		list = new int [m];
		dfs(0);
        // BufferedWriter클래스의 경우 프로그램이 종료하기 전에 flush()를 수행해주어야
        // 올바르게 출력값이 나온다고 한다. 왜 그런지는 자세히는 모르겠다..
        
		br.close();
		bw.flush();
		bw.close();
	}
	
}