[백준_15666번] N과 M (12)

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

15666번: N과 M (12)

[문제]

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.입력

 

[입력 조건]

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_15666 {
	static int n,m;
	static int[] arr,print;
	// 입력 순서를 지키기 위해 HashSet이 아닌 LinkedHashSet을 사용해야 한다. 
	static LinkedHashSet<String> set=new LinkedHashSet<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		arr=new int[n];
		print=new int[m];
		
		for(int i=0;i<n;i++)
			arr[i]=sc.nextInt();
		
		Arrays.sort(arr); // 정렬된 배열 사용
		dfs(0,0);
		
		// LinkedHashSet에 저장된 수열 출력
		Iterator iter=set.iterator();
		while(iter.hasNext())
			System.out.println(iter.next());
	}
	
	static void dfs(int depth, int start) {
		// 선택된 m개의 숫자로 만들어진 수열을 LinkedHashSet에 저장
		if(depth==m) {
			StringBuilder sb=new StringBuilder();
			for(int i:print)
				sb.append(i).append(" ");
			set.add(sb.toString());
			return;
		}
		
		// 위치만 바뀌고 같은 숫자를 선택한 경우는 제외해야 하므로 재귀 호출 범위 조정
		for(int i=start;i<n;i++) {
			print[depth]=arr[i];
			dfs(depth+1,i);
		}
	}
}

 

[고찰]

 N과 M 시리즈 마지막 문제이다. 해당 문제는 이전에 풀었던 15665번 N과 M 11번째 문제에서 약간만 변형하면 된다. 이번 문제는 위치만 바뀌고 같은 숫자를 선택한 경우는 제외해야 하기 때문에 dfs 함수에 start 매개변수를 사용하여 숫자 선택 범위를 조정하는 방법으로 코드를 짜면 정답 처리를 받을 수 있다.