[백준/Java] 1038. 감소하는 수

 

🔗 문제 링크: https://www.acmicpc.net/problem/1038

 

 

🔍 해결 과정

조합을 활용하여 감소하는 숫자를 구하였습니다. 감소하는 숫자이므로 각 자리마다 9부터 0까지 선택하며 감소하는 형태의 숫자로 만들었습니다.

해결 과정은 다음과 같습니다.

1️⃣ 최대 감소하는 숫자는 9876543210이므로 10자리 숫자이다. 즉 한자리부터 10자리까지 반복문을 구성하면서 조합을 진행한다.
2️⃣ Long 자료형으로 구성된 List 자료구조 result를 만들어 감소하는 숫자를 담아낼 공간을 마련한다.
3️⃣ 반복문을 활용하여 한자리의 경우부터 10자리 경우까지 조합을 진행한다.
3️⃣ 배열을 통해(코드에서 arr 배열) 각 자리마다 숫자를 하나씩 선택하며 감소하는 형태의 숫자를 완성하고 이를 result에 담아낸다.
4️⃣ 순서를 위해 result를 오름차순 정렬을 진행한다.
5️⃣ 정렬을 완료 후 인덱싱을 통해 결과를 찾아낸다.

 

 

---

✏️ 코드

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

public class Main {

    private static final int INVALID = -1;
    private static List<Long> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringBuilder answer = new StringBuilder();

        for (int len = 1; len <= 10; ++len) {
            comb(new int[len], 0, 9, len);
        }

        Collections.sort(result);

        if (result.size() <= n) {
            answer.append(INVALID);
        } else {
            answer.append(result.get(n));
        }
        bw.write(answer.toString());
        bw.flush();
    }

    private static void comb(int[] arr, int idx, int start, int m) {
        if (idx >= m) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < m; ++i) {
                sb.append(arr[i]);
            }

            result.add(Long.parseLong(sb.toString()));
            return;
        }

        for (int i = start; i >= 0; --i) {
            arr[idx] = i;
            comb(arr, idx + 1, i - 1, m);
            arr[idx] = 0;
        }
    }
}