[백준](1038번) 감소하는 수 : 골드 문제 첫 도전

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

 

감소하는 수 찾기 문제입니다.

문제를 보자마자 브루트 포스(무차별 대입)이라는 느낌이 들었습니다.

 

브루트 포스는 경우의 수를 최대한 필터링 해 시간을 단축시키는 것이 목적입니다.

 

여기서 추려낼 수 있는 가장 중요한 알고리즘은 이것입니다.

 

오른쪽 자리수가 왼쪽보다 같거나 크면, 그 단위는 건너뜀.

 

무슨 말인가 하면,

 

10의 경우 오른쪽의 0이 왼쪽의 1보다 작으므로 감소하는 수 O

11의 경우 오른쪽의 1이 왼쪽의 1과 같으므로 감소하는 수 X

 

이런 경우 나머지 1의 자리는 볼 것도 없이 전부 패스하고, 20부터 비교하면 됩니다.

 

그렇다면, 지금 비교하고 있는 자리가 몇 번째 자리인지, 이를 알려주는 변수가 필요하겠죠.

자리수의 영어명을 따서 digit이라고 하겠습니다.

 

또한 기본적으로, 0부터 시작하여 기본적으로 1씩 증가시킬 카운트 변수도 필요할 것입니다.

이 놈을 n라고 하죠.

 

n을 1씩 증가시키며 감소하는 수가 나오면, 이게 몇 번째 감소하는 수인지는 어떻게 알 수 있을까요?

그것을 카운트 하기 위한 변수를 cnt라고 합시다.

 

N번째 감소하는 수를 입력받을 변수명은 그대로 N이라고 합시다.

 

 

흐름은 이렇습니다.

 

while을 돌며 N번째 감소하는 수가 나올 때까지 n를 증가시키다가,

N과 cnt가 같아지는 순간 break를 하고 그 때의 n을 출력하면 됩니다.

 

 

필요한 정보는 모두 마련됐습니다.

바로 소스로 구현해보도록 합시다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int cnt = 10;
		long n = 20; // cnt = 감소하는 수의 개수, n = 1씩 증가하는 수
		String[] spl;
		Boolean gam = true; //

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		if (N >= 1023) {
			System.out.println("-1");
		} else if (N <= 10) { // 한 자리~10까지는 그대로 출력
			System.out.println(N);
		} else { // 11부터는
			while (true) {
				spl = Long.toString(n).split(""); // 숫자 한자리씩 쪼개 넣기
				gam = true;
				for (int i = 0; i < spl.length - 1; i++) { // 자릿수-1번만큼 비교하기
					if (Integer.parseInt(spl[i]) <= Integer.parseInt(spl[i + 1])) { // 감소하는 수가 아니면 다음 수 비교하기

						String str = "";
						if (Integer.parseInt(spl[i]) == Integer.parseInt(spl[i + 1])) { // Ex) [33]00->[40]00
							spl[i] = Integer.toString(Integer.parseInt(spl[i + 1]) + 1);
							spl[i + 1] = "0";
							for (int j = 0; j < spl.length; j++) {
								str = str.concat(spl[j]);
							}
							n = Long.parseLong(str) - 1;
						}
						gam = false; // 감소수 X
						break; // 감소수X면 더 이상 비교할 필요 없으므로 for문 탈출 100 ->199, 200->209, 220->300
					}
				}

				if (gam == true) { // n은 감소하는 수인가?
					cnt++; // 맞으면 cnt+1
				}

				if (cnt == N)
					break; // N==55
				else {
					n++;
				}
			}
			System.out.println(n);
		}

	}

}