[BOJ - JAVA] 15665 - N과 M 11(백트래킹)

# 주소

https://www.acmicpc.net/submit/15665/33730022

로그인

 

# 문제

 

# 문제 해설 및 코드 리뷰

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

public class Main {
	public static int[] arr,ans;
	public static int N, M;
	public static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();
    public static LinkedHashSet<String> set;
	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];
		ans = new int[N];
		st = new StringTokenizer(br.readLine());
        set = new LinkedHashSet<>();
        for(int i = 0; i < N; i++) {
        	ans[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(ans);
		dfs(0);
		StringBuilder sb2 = new StringBuilder();
		set.stream().forEach(i -> sb2.append(i + '\n'));
		System.out.println(sb2);
	}
 
	public static void dfs(int depth) {
		if (depth == M) {
			StringBuilder sb = new StringBuilder();
			for (int val : arr) {
				sb.append(val + " ");
			}
			set.add(sb.toString());
			sb.append('\n');
			return;
		}
		for(int i = 0; i < N; i++) {
				arr[depth] = ans[i];
				dfs(depth+1);
		}
	}
}

크게 어렵지 않았던 문제입니다. 다만 BufferedReader로 입력 받고  Sys.out으로 출력을 하다보니 계속해서 시간초과가 뜨는 바람에 BufferedWriter로 출력하려고 하였으나 String 타입을 BufferedWriter로 출력하는 방법을 못찾아서 다른 방식으로 출력했습니다.

 

출력 예제에서 알 수 있듯이 입력된 9 7 9 1 중  1 7 9 만 활용되는 것을 보아 LinkedHashSet이 무조건 필요하단 것을 알 수 있습니다. 따라서 set을 생성하여 sb에 담고 문자열로 담았습니다. 그리고 출력할 때 set.stream().foreach문을 써서 

람다식을 이용하여 출력을 진행했습니다. 

set을 그대로 출력하면 [ ... ... ... ] 와 같은 형태가 나오기 때문에 절대로 set을 그대로 출력하지 않고 sb2라는 StringBuilder의 sb2라는 생성자를 만든 후 append하여 담아주시기 바라겠습니다.