[BOJ] 1038. 감소하는 수

Hyodong Lee·2022년 2월 21일
0

알고리즘

목록 보기
11/32

[작성일]

  • 2022-02-22

[분류]

  • 재귀함수


[문제링크]

[요구사항]

  • N번째 감소하는 수를 구하라.


[풀이]

감소하는 수의 조건은 뒤에 오는 숫자가 앞에 숫자보다 작으면 된다.
이것을 생각해서 지금 숫자 num의 1의자리(곧 10의자리가 될 숫자)보다 작은 수만 새로 1의 자리에 들어갈 수 있기 때문에 새로 고려해서 추가해준다. 그런 식으로 모든 수를 구하고 정렬해주면 N번째 수를 구할 수 있다.



[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N;
    static ArrayList<Long> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();

        // 10보다 작은 경우
        if (N < 10) System.out.println(N);
        // 1022번째 숫자가 9876543210이기 때문에 1022번째보다 클 경우 -1
        else if (N > 1022) System.out.println(-1);
        // 재귀함수를 이용해서 9876543210이하의 감소하는 수를 모두 만들어준다.
        else {
            for (int i = 0; i < 10; i++) {
                makeNum(i);
            }
            Collections.sort(list);
            System.out.println(list.get(N));
        }
    }

    public static void makeNum(long num) {
        if (num > 9876543210L) return;
        list.add(num);
        for (int i = 0; i < num % 10; i++) {
            makeNum((num * 10) + i);
        }
    }
}

[느낀점]

숫자 바로 뒤에 올 숫자를 결정하면 되는 단순한 재귀함수 문제였는데 다음부터는 더 빨리 생각날 수 있도록 더 열심히 연습해야겠다.

profile
사용자가 신뢰할 수 있는 튼튼한 서비스 개발을 지향하는 예비 개발자입니다.

0개의 댓글