[백준] 15652번 : N과 M (4) - JAVA [자바]

www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

---

• 문제

 

 

 

 

 

N과 M (2) 문제를 기억하신다면 아마 금방 풀 수 있을 것이다. 다만 이 번 문제는 약간 다른 점이라 한다면 '비내림차순'인 수열을 출력해야한다는 점이다. (오름차순과 비내림차순은 다르다) 즉, 중복 여부를 고려하지 않는다. (중복허용)

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

그동안 필자의 포스팅에서 N과 M 시리즈들을 모두 보셨다면 이 번 문제 또한 그리 어렵지 않게 풀 수 있을 것이다. 그래도 혹시 모르니 참고 포스팅 링크를 올려놓도록 하겠다.

 

 

st-lab.tistory.com/115#알고리즘

[백준] 15650번 : N과 M (2) - JAVA [자바]

 

위 포스트를 보셨다면 알겠지만, 이전의 N과 M (2) 에서는 at 이라는 시작점 변수를 두었고, 재귀호출 할 때마다 오름차순으로 탐색할 수 있도록 반복문의 i 값에 +1 을 더한 값을 넣어주며 재귀호출을 해주었다. N과 M (2) 에서 사용한 코드는 아래와 같다.

public static void dfs(int at, int depth) {
	if (depth == M) {
		/*
		 출력문
		*/
	}
        
	for (int i = at; i <= N; i++) {
		arr[depth] = i;
		dfs(i + 1, depth + 1);
	}
}

 

 

이 번 문제는 '비내림차순'이므로 중복도 허용이 된다는 것이다. 그럼 탐색을 어떻게 해주면 될까? 반복문 내에서 i 값을 1 더하여 재귀호출을 해주는 것이 아닌 그냥 i 값을 인자로 넘겨 재귀호출 해주면 되지 않은가?

즉, 우리가 수정할 값은 dfs 재귀호출 시에 넘겨줄 인자만 바꿔주면 된다!

 

public static void dfs(int at, int depth) {
	if (depth == M) {
		/*
		 출력문
		*/
	}
        
	for (int i = at; i <= N; i++) {
		arr[depth] = i;
		dfs(i, depth + 1);
	}
}

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

알고리즘은 위 설명대로 풀 것이다. 다만 입출력을 달리하여 성능을 확인해보도록 하겠다. 다행이 필자가 테스트 해본 결과 Scanner 와 반복출력을 하더라도 시간초과가 뜨지는 않았다. 그러나 느린 방법이라는 건 변함이 없으니, 한 번 성능을 직접 눈으로 확인할 수 있도록 비교해서 올려놓겠다.

 

3가지 방법은 아래와 같다.

 

1 . Scanner + 반복출력

2. Scanner + StringBuilder

3. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + 반복출력]

 

import java.util.Scanner;

public class Main {

	public static int N, M;
	public static int[] arr;

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		N = in.nextInt();
		M = in.nextInt();
		arr = new int[M];

		dfs(1, 0);

	}

	public static void dfs(int at, int depth) {

		if (depth == M) {
			for (int val : arr) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}

		for (int i = at; i <= N; i++) {
			arr[depth] = i;
			dfs(i, depth + 1);
		}

	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다. 이렇게 풀다보니 이쯤되면 사람들이 Scanner로도 풀려나 싶긴 하지만,, 혹시 모르니! Scanner 를 사용한 방법도 꾸준히 올리겠다.

 

앞서 알고리즘에서 말했듯이 재귀호출을 해줄 때 오름차순이 아닌 '비내림차순'이기 때문에 i 값을 1 증가시키는 것이 아닌, i 값 그대로 넘겨준다.

 

 

---

- 방법 2 : [Scanner + StringBuilder]

 

 

 

출력 방법을 반복하여 출력하는 방버 대신 StringBuilder을 사용하여 풀이하는 방법이다.  다시 한 번 언급하겠지만, 단순 몇 줄 출력이면 반복적으로 출력해주어도 큰 차이는 없지만, 출력문이 많아질수록 출력스트림으로 데이터를 반복적으로 접근, 전송, 출력을 해주기 때문에 시간이 지연될 수 밖에 없다. 그러니 BufferedWriter을 쓰거나 StringBuilder을 사용하여 출력 성능을 개선 하는 것이 좋다.

 

 

import java.util.Scanner;

public class Main {

	public static int N, M;
	public static int[] arr;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		N = in.nextInt();
		M = in.nextInt();
		arr = new int[M];

		dfs(1, 0);
		System.out.println(sb);

	}

	public static void dfs(int at, int depth) {

		if (depth == M) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i = at; i <= N; i++) {
			arr[depth] = i;
			dfs(i, depth + 1);
		}

	}

}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉽지 않았을까,,, 만약 어려웠다면 직접 디버그하면서 변수들의 값 변화를 하나씩 체크해보는 것도 좋을 것이다.

 

---

- 방법 3 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static int N, M;
	public static int[] arr;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[M];

		dfs(1, 0);
		System.out.println(sb);

	}

	public static void dfs(int at, int depth) {

		if (depth == M) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i = at; i <= N; i++) {
			arr[depth] = i;
			dfs(i, depth + 1);
		}

	}

}

 

 

 

물론 문자열 분리 방법은 이 것만 있지는 않으니 여러분들이 자유롭게 변경하여 시도해보는 것도 좋을 것 같다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 20692017  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 20692014  -  방법 2 : Scanner + StringBuilder

채점 번호 : 20692010  -  방법 1 : Scanner + 반복출력

 

 

입력 방법의 차이와 출력 방법의 차이에서 성능이 눈에띄게 다르다는 점을 확인 할 수 있다.

더군다나 출력에서 더 큰 차이를 볼 수 있다.

---

• 정리

 

 

백트래킹 카테고리에서의 N과 M은 이제 끝났다. 4개의 N과 M을 제대로 이해하고 풀었다면, 이 후의 백트래킹 문제 또한 크게 어렵지 않게 풀 수 있을 것이다. 기본적으로 백트래킹의 경우 조건만 잘 이해하고 해당 조건만 추가하여 탐색을 하도록 구현을 하면 되기 때문에 더욱이 N과 M 의 4개의 문제를 잘 이해해야 한다.

 

혹여 이해가 안되거나, 어려운 점이 있다면 댓글 남겨주시면 최대한 빠르게 답변드리겠다.