[BOJ - JAVA] 15663 - N과 M 9(백트래킹)

# 주소

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

# 문제

 

# 문제 해설 및 코드 리뷰

package first;
import java.io.*;
import java.util.*;
import java.util.Scanner;

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];
		set = new LinkedHashSet<>();
		st = new StringTokenizer(br.readLine());
        visit = new boolean[N];
        
        for(int i = 0; i < N; i++) {
        	ans[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(ans);
		dfs(0);
        set.forEach(System.out::println);
	}
 
	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++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = ans[i];
				dfs(depth+1);
				visit[i] = false;
			}
		}
	}
}

이번에야 BufferedReader로 입력문을 완성했습니다. 이 블로그에선 처음 작성했지만 throws IOException으로 예외처리를 하고 나서 StringTokenizer 메소드를 이용하여 다음 ans배열을 입력 받습니다.

 

그리고 여기서 핵심인 LinkedHashSet<>을 이용하여 코딩을 해야합니다.

다음 set 들을 정리해보았습니다.

Set : 중복 값을 삽입할 수 없고, 특정한 순서를 가지고 있지 않다는 특징이 있습니다.

HashSet : Set 인터페이스의 구현 클래스입니다. 순서가 유지되지 않고 넣은 값의 hashcode에 따라 순서가 나옵니다. 그리고 hashcode 와 key값만 알고 있으면 찾을 수 있기 때문에 상대적으로 검색이 빠른 편에 속합니다.

cf)ArrayList : 배열 기반 클래스이고 중복이 허용됩니다. 배열의 정렬이 자동으로 이루어지며 요소의 위치를 파악하기는 쉬우나 여러번 순회를 통해 값을 찾아야 하므로 검색속도가 느린 편에 속합니다.

LinkedHashSet : 중복을 허용하지 않지만 add 한 순서대로 값이 저장됩니다.

TreeSet : 오름차순으로 값을 정렬해 가지고 있으며, 다른 set보다 대량의 데이터 검색 시 빠릅니다.

 

여기서는 중복을 허용하지 않아야 하고 각 배열들을 입력받는 대로 오름차순으로 정렬할 것이기 때문에 LinkedHashSet을 이용하도록 하겠습니다. 그리고 dfs함수의 인자는 depth로 설정하여 StringBuilder에 String 형태로 변환하여 삽입시킵니다. 이것은 for문에서 visit[i]가 false일 때만 ans값을 가져와 arr에 데이터를 삽입한 뒤 dfs(depth+1)를 재귀호출하여 중복되지 않게끔 출력하면 되겠습니다.

LinkedHashSet을 이용하는 것이 바로 생각이 안날 뿐이지, 다른 알고리즘 구현은 쉬운 편에 속합니다.