[백준/15649][Java] N과 M(1)

문제

15649번: N과 M (1)

가장 기본적인 백트래킹 문제이다. 

func라는 함수의 역할은, k번째 수를 정하는 것이다.

k번째 수를 정하고, k+1의 수를 재귀적으로 정해준다.

코드

package algo0314;

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

public class B15649_N과M1 {
	static int n, m;
	static int[] arr;
	static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

	static void func(int k) {
		if (k == m) {
			for (int i = 0; i < m; i++) {
				sb.append(arr[i] + " ");
			}
			sb.append('\n');
		} else {
			for (int i = 0; i < n; i++) {
				if (!visited[i]) {
					visited[i] = true;
					arr[k] = i + 1;
					func(k + 1);
					visited[i] = false;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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[n];
		visited = new boolean[n];
		func(0);
        System.out.println(sb);

	}

}

 

StringBuilder을 쓰고 안 쓰냐에 따른 시간 차이

처음 제출한게 System.out.println를 사용해 하나씩 출력한 것이고, 두번째로 제출한게

    static StringBuilder sb = new StringBuilder();

 를 사용해서 한번에 출력한 것인데 출력 속도 차이가 10배 이상 나는 것을 확인할 수 있다.

웬만하면 StringBuilder을 사용하기로 하자..