[백준_1174번] 줄어드는 숫자

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

1174번: 줄어드는 숫자

[문제]

 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. (가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.)

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1174 {
	static int[] num= {9,8,7,6,5,4,3,2,1,0};
	static ArrayList<Long> arr=new ArrayList<>();
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		dfs(0,0);
		Collections.sort(arr); // n번째 수를 찾기 위해 정렬한다.
		
		/*
		 * 숫자는 겹치게 선택할 수 없기 때문에 
		 * 10개의 숫자를 선택하냐 선택하지 않느냐 총 1024개의 경우의 수가 나온다.
		 * 이 수를 넘어가는 n을 입력받는다면 n번째로 작은 줄어드는 수가 존재할 수 없기 때문에 -1을 출력한다.
		 */
		if(n>1023)
			System.out.println(-1);
		else
			System.out.println(arr.get(n-1));
	}
	
	static void dfs(long sum, int index) {
		// sum이 이전에 나온적이 없는 수라면 arr에 저장
		if(!arr.contains(sum))
			arr.add(sum);
		
		// num 배열로 모두 탐색했다면 재귀호출 종료
		if(index>=10)
			return;
		
		/*
		 * num 배열의 현재 수를 선택 하느냐, 선택하지 않느냐 
		 * 두 가지 경우만 존재하므로 각각의 경우 모두 재귀호출 해주면 된다.  
		 */
		dfs(sum*10+num[index],index+1); // 현재 수를 선택하는 경우
		dfs(sum,index+1); // 현재 수를 선택하지 않는 경우
	}
}

 

[고찰]

 이번 문제는 스스로 풀어보다 어떻게 자릿수를 늘려가며 모든 수를 탐색할지 아이디어가 떠오르지 않아 다른 사람의 코드를 참고하여 해결했다. 이번 문제의 핵심은 9부터 0을 내림차순으로 저장한 배열을 사용하는 것이다. 이렇게 내림차순으로 저장된 배열을 사용하여 수를 만들게 되면 만들어진 수가 줄어드는 수인지 따로 확인할 필요가 없어진다. 

 줄어드는 수를 만드는 방법은 현재 배열의 값을 선택하느냐, 선택하지 않느냐이다. 현재 배열의 값을 선택한다면 자릿수를 하나 밀어주고 현재 배열의 값을 더해주면 되고, 선택하지 않는다면 배열의 인덱스만 증가시켜주고 재귀호출 하면 된다. 이렇게 경우의 수는 현재 배열의 값을 선택하느냐, 선택하지 않느냐 2가지만 존재하므로 총 2^10=1024 가지의 경우의 수가 나올수 있다. 이 수를 넘어가면 n번째의 줄어드는 숫자를 찾을 수 없으므로 -1을 출력해야 한다. 

 스스로 풀이를 시도했을 때는 숫자를 만들 생각만 했지 줄어드는 숫자를 찾을 수 없는 경우는 고려하지 못했다. 문제를 좀더 깊히 들여다보는 습관을 길러야겠다.