[ 백준 15651 ] N 과 M (3)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
  
  

입력

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력	예제 출력
4 2	1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4

 

풀이

처음에 풀고 제출했을 때에는 시간초과 오류가 났다. 원인을 알아보니 보통 Scanner 와 System.out.print을 사용하는 부분에서 시간 소모가 커지면서 나기 때문이라고 한다. 아마 이번 문제에서는 Scan 되는 수는 2개 밖에 없기 때문에 Scan 쪽 문제라기 보다는 print 하는 부분에서의 시간 소모가 큰 것이 문제일 것 같다고 생각했다.
    -> ( 테스트 해본 결과 Scanner 는 두고 print 부분을 BufferedWriter로만 바꿔도 통과!! )

그리하여 원래 코드의 Scanner 사용 부분은 BufferedReader를 사용하였고, System.out.print 부분은 BufferedWriter로 바꿔서 코드를 제출하였더니 통과가 되었다.

✔️ 앞으로 시간이 많이 소모될 것으로 예상되는 문제에서는 Scanner 와 System.out.print 대신 BufferedReader와 BufferedWriter를 활용할 것‼️

[ JAVA ]

	// 첫번째 정답 -> 시간초과
	package baekjoon_Algorithm;
	import java.util.*;
	public class baekjoon_15651 {
	static int[] arr;
	static int N, M;
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	N = scan.nextInt();
	M = scan.nextInt();
	arr = new int[M];
	solution(0);
	}
	public static void solution(int index) {
	if (index == M) {
	for (int s : arr) {
	System.out.print(s + " ");
	}
	System.out.println();
	} else {
	for (int i = 1; i <= N; i++) {
	arr[index] = i;
	solution(index + 1);
	}
	}
	}
	}

view raw N 과 M (3)_1.java hosted with ❤ by GitHub

	package baekjoon_Algorithm;
	import java.util.*;
	import java.io.*;
	public class baekjoon_15651 {
	static int[] arr;
	static int N, M;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String s = br.readLine();
	N = Integer.parseInt(s.split(" ")[0]);
	M = Integer.parseInt(s.split(" ")[1]);
	arr = new int[M];
	solution(0);
	bw.close();
	}
	public static void solution(int index) throws IOException{
	if (index == M) {
	for (int s : arr) {
	bw.write(s + " ");
	}
	bw.newLine();
	} else {
	for (int i = 1; i <= N; i++) {
	arr[index] = i;
	solution(index + 1);
	}
	}
	}
	}

view raw N 과 M (3)_2.java hosted with ❤ by GitHub