15663 - N과 M 9(백트래킹)

15663 - N과 M 9(백트래킹)

# 주소

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

# 문제

# 문제 해설 및 코드 리뷰

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 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('

'); 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을 이용하는 것이 바로 생각이 안날 뿐이지, 다른 알고리즘 구현은 쉬운 편에 속합니다.

from http://codingrapper.tistory.com/21 by ccl(A) rewrite - 2021-09-25 19:27:11