[BOJ-1038][완전 탐색/조합] 감소하는 수 - Java

문제 바로가기

1038번: 감소하는 수

 

N 번째 감소하는 수를 구하는 문제입니다.

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

public class Main {
	static int[] numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	static List<Integer> nums = new ArrayList<>();
	static List<String> depthList;
	
	public static void comb(int depth, int idx, int cnt) {
		if(cnt == depth) {
			Collections.sort(nums, Collections.reverseOrder());
			StringBuilder sb = new StringBuilder();
			for(int n : nums) sb.append(n);
			
			depthList.add(sb.toString());
			return;
		}
		
		for(int i = idx; i < numbers.length; i++) {
			nums.add(numbers[i]);
			comb(depth, i + 1, cnt + 1);
			nums.remove((Integer)numbers[i]);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Map<Integer, String> map = new TreeMap<>();
		int mapIdx = 0;
		
		for(int i = 1; i <= 10; i++) {
			depthList = new ArrayList<>();
			comb(i, 0, 0);
			Collections.sort(depthList);
			
			for(String l : depthList) map.put(mapIdx++, l);
		}
		
		System.out.println(map.get(N) != null ? map.get(N) : -1);
	}
}

 

감소하는 수는 총 몇개일까요?

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 집합에서 공집합을 제외한 모든 부분집합 개수와 같습니다.

감소하는 수에 포함된 수는 중복된 수가 있으면 안되겠지용. 즉, 2^10 - 1개가 됩니다.

 

그러니깐 깔끔하게 조합으로 모든 감소하는 수를 만들어봅시다. 

depth(자릿수) 1~10까지 돌려줍시다. 

감소하는 수니깐 수를 다 고르면 내림차순으로 정렬해주어야겠지요.

정렬한 수를 depthList에 넣어주고 숫자를 다 구하면 얘를 또 정렬해야겠지용.

이 때 map에 넣어주었습니다.

 

감소하는 수를 다 만들고 map에 N이 key에 있는지만 체크하면 끝입니당!

 

 

감사합니다~!~!