[백준][JAVA] 15657번 N과 M (8)

15657번: N과 M (8)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static int N, M, A[], R[];
	static Set<String> s = new HashSet<>();
	
	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());
		
		A = new int[N];
		R = new int[M];
		
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(A);
		
		combination(0, 0);
	}

	static void combination(int start, int cnt) {
		
		if (cnt == M) {
			StringBuilder sb = new StringBuilder();
			
			for (int i = 0; i < M; i++) {
				sb.append(R[i]).append(" ");
			}
			sb.append("\n");
			
			String result = sb.toString();
			
			if (!s.contains(result)) {
				System.out.print(result);
				s.add(result);
			}
			
			return;
		}
		
		for (int i = start; i < N; i++) {
			R[cnt] = A[i];
			combination(i, cnt + 1);
		}
	}

}

풀이

우선 조합 알고리즘을 재귀로 구성했다.

기저조건에 도달할 경우, 백트래킹을 통해 재귀 호출을 중단하고 출력 조건에 해당하는지 검사한다.

검사는 출력 결과를 모아놓은 집합에 해당 문자열이 있는지를 체크하는 방식으로 진행했다.

출력 조건에 해당하면 결과를 출력하고 출력 목록을 저장하는 집합에 저장하여 문제를 해결할 수 있었다.