백준 11659번
https://www.acmicpc.net/problem/11659

문제

---

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

생각하기

---

중복되지 않은 수열을 뽑아내기 위해서는 출력을 하기 위해 완성된 StringBuilder를 Hashset를 통해서 검증해야 한다.

Hashset은 중복된 값 자체가 들어갈 수 없기 때문에 메모리적인 측면에서도 효율적이고, 중복이 되지않는다는 점에서 검사하기 매우 적합하다.

동작

		if(depth == M) {
			StringBuilder temp = new StringBuilder();
			for(int i=0; i<M; i++) {
				temp.append(ans[i]).append(' ');
			}

			if(!set.contains(temp.toString())) {
				sb.append(temp).append('\n');
				set.add(temp.toString());
			}
			return;
		}

depth == M조건에서 재귀 종료 조건을 만들고

temp를 통해서 출력할 문자열을 만들고, set에 해당 문자열이 포함되어있을 경우 곧바로 return한다. set에 출력되는 문자열을 모두 저장해두면 중복여부를 파악할 수 있다.

코드

---

Java

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

public class Main {
	static int N, M;
	static int arr[];
	static int ans[];
	static boolean visit[];
	static HashSet<String> set = new HashSet<>();
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		ans = new int[M];
		visit = new boolean[N];

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		DFS(0);

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	} // End of main

	static void DFS(int depth) {

		if(depth == M) {
			StringBuilder temp = new StringBuilder();
			for(int i=0; i<M; i++) {
				temp.append(ans[i]).append(' ');
			}

			if(!set.contains(temp.toString())) {
				sb.append(temp).append('\n');
				set.add(temp.toString());
			}
			return;
		}

		for(int i=0; i<N; i++) {	
			if(visit[i]) continue;
			visit[i] = true;
			ans[depth] = arr[i];
			DFS(depth+1);
			visit[i] = false;
		}

	} // End of DFS
} // End of Main class

Kotlin

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

public class Main {
	static int N, M;
	static int arr[];
	static int ans[];
	static boolean visit[];
	static HashSet<String> set = new HashSet<>();
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		ans = new int[M];
		visit = new boolean[N];

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		DFS(0);

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	} // End of main

	static void DFS(int depth) {

		if(depth == M) {
			StringBuilder temp = new StringBuilder();
			for(int i=0; i<M; i++) {
				temp.append(ans[i]).append(' ');
			}

			if(!set.contains(temp.toString())) {
				sb.append(temp).append('\n');
				set.add(temp.toString());
			}
			return;
		}

		for(int i=0; i<N; i++) {	
			if(visit[i]) continue;
			visit[i] = true;
			ans[depth] = arr[i];
			DFS(depth+1);
			visit[i] = false;
		}

	} // End of DFS
} // End of Main class