[백준_15664번] N과 M (10)

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

15664번: N과 M (10)

[문제]

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_15664 {
	// 입력 순서를 지키기 위해 HashSet이 아닌 LinkedHashSet을 사용해야 한다. 
	static LinkedHashSet<String> set=new LinkedHashSet<>();
	static int n,m,arr[],print[];
	static boolean[] visited;
	
	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];
		visited=new boolean[n];
		
		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;
		}
		
		// n개의 숫자중 m개의 숫자를 중복없이 선택
		for(int i=start;i<n;i++) {
			if(!visited[i]) {
				visited[i]=true;
				print[depth]=arr[i];
				dfs(depth+1,i+1);
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

N과 M 시리즈 10번째 문제이다. 이번 문제는 이전에 풀었던 9번째 문제와 비슷하다. 입력되는 숫자는 중복을 허용하기 때문에 LinkedHashSet을 사용하여 만들어진 수열의 중복을 없애주는 것 뿐만 아니라 입력된 수열의 순서를 유지하도록 한다.