BOJ 15651 - N과 M (3)

입력

• 자연수 N과 M 입력 (1 ≤ M ≤ N ≤ 8)

출력

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 출력 (중복 X, 각 수열은 공백으로 구분해서 출력, 사전 순으로 증가하는 순서로 출력)
• 같은 수를 여러 번 골라도 됨 (15649번 : N과 M (1) 문제와 다른 부분)

풀이 방법

• 15649번 문제와 같은 방법으로 풀되, 같은 수를 여러 번 골라도 되므로 visit[] 배열을 이용하여 방문 여부를 체크할 필요가 없음
• [코드 1]에서 Scanner를 사용하여 입력을 받고, cnt가 M이 될 때마다 System.out.print()를 이용하여 출력을 해줬더니 시간이 초과됨
• 시간 초과 문제를 해결하기 위해 [코드 2]에서는 Scanner 대신 BufferedReader를 사용하여 입력을 받고, System.out.print() 대신 BufferedWriter를 사용하여 출력함

코드

[코드 1] - 시간 초과 (Scanner 이용)

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] ans;
	
	public static void backtracking(int cur, int cnt) {
		ans[cnt]=cur;	// 수열 배열에 현재 숫자 저장
		
		if(cnt==M) {	// M개의 숫자에 방문 완료했으면
			for(int i=1;i<M+1;i++) {	// 수열 출력
				System.out.print(ans[i]+" ");
			}
			System.out.println();	// 수열 구분
			return;
		}
		
		for(int i=1;i<N+1;i++) {// 반복해서 탐색 (15649번 문제와 다른 부분: 수열을 오름차순으로 만들기 위함)
			backtracking(i, cnt+1);	// 방문visit[i]=0;	// 다음 탐색을 위해 초기화
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();	// 자연수 N 입력
		M=sc.nextInt();	// 자연수 M 입력
		ans=new int[N+1];	// 수열 저장할 배열
		
		for(int i=1;i<N+1;i++) {
			backtracking(i, 1);	// 백트래킹
		}
		
		sc.close();
	}
}

[코드 2] - BufferedReader와 BufferedWriter 이용

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

public class Main {
	static BufferedWriter bw;
	static int N, M;
	static int[] ans;
	
	public static void backtracking(int cur, int cnt) throws IOException {
		ans[cnt]=cur;	// 수열 배열에 현재 숫자 저장
		
		if(cnt==M) {	// M개의 숫자에 방문 완료했으면
			for(int i=1;i<M+1;i++) {	// 수열 출력
				bw.write(ans[i]+" ");
			}
			bw.write("\n");	// 수열 구분
			return;
		}
		
		for(int i=1;i<N+1;i++) {// 반복해서 탐색 (15649번 문제와 다른 부분: 수열을 오름차순으로 만들기 위함)
			backtracking(i, cnt+1);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader 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());	// 자연수 N 입력
		M=Integer.parseInt(st.nextToken());	// 자연수 M 입력
		ans=new int[N+1];	// 수열 저장할 배열
		
		for(int i=1;i<N+1;i++) {
			backtracking(i, 1);	// 백트래킹
		}
		
		bw.flush();
		bw.close();
	}
}