[Java] 백준 1174번 : 줄어드는 수

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

예제 입력 1

1

예제 출력 1

0

예제 입력 2

19

예제 출력 2

42

예제 입력 3

500000

예제 출력 3

-1

 

소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static int N;
	private static int[] num= {9,8,7,6,5,4,3,2,1,0};
	private static List<Long> numbers=new ArrayList<Long>();
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		
		if(N>1023) System.out.println(-1);
		else {
			combination(0,0);
			Collections.sort(numbers);
			System.out.println(numbers.get(N-1));
		}
		
	}

	public static void combination(int idx, long sum) {
		
		if(!numbers.contains(sum)) numbers.add(sum);
		if(idx==10) return;

		combination(idx+1, sum*10+num[idx]);
		combination(idx+1, sum);
	}
}

9부터 0까지의 값을 차례대로 가지고 있는 배열을 하나 만들고, 배열의 각 요소를 포함하거나 포함하지 않는 모든 경우의 수를 구해보면 총 2^10-1=1023가지가 존재함을 알 수 있습니다.

1. combination 메서드를 재귀를 통해 구현하여 가능한 모든 줄어드는 수를 구하여 numbers 리스트에 저장합니다.

    1-1. idx가 10이 되면 리턴

    1-2. 배열의 idx번째 값을 포함하는 경우 재귀 수행

    1-3. 배열의 idx번째 값을 포함하지 않는 경우 재귀 수행

2. numbers 리스트를 오름차순 정렬합니다.

3. 찾는 위치의 수를 출력합니다.

 

출처 : https://subin-programming.tistory.com/325