백준 1038번: 감소하는 수 (JAVA)

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

 

---

 

풀이

 

1. bfs 등의 탐색 

처음에 큐에 0~9를 넣은 후, (숫자의 맨 앞자리 + 1)부터 9까지 붙인 수를 큐에 넣어서 bfs 진행

 

2. 비트마스킹

생각해보면 감소하는 수에서 0~9는 각각 최대 한 번만 나올 수 있으므로, 감소하는 수는 1000000000(2) = 9, 1100000000(2) = 98과 같이 10자리의 2진수로 대응 가능하다:

유의할 점으로는, 0000000000(2) = 0000000001(2) = 0이니 한 번만 세주자.

 

 

코드

풀이 1. 탐색

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Long> nums = new ArrayList<>();
        Queue<Long> queue = new ArrayDeque<>();
        for (int i = 0; i < 10; i++) {
            queue.add((long) i);
            nums.add((long) i);
        }
        int cnt = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                long temp = queue.poll();
                for (long i = temp / ((long) Math.pow(10, cnt)) + 1; i < 10; i++) {
                    long nxt = temp + i* ((long) Math.pow(10, cnt+1));
                    nums.add(nxt);
                    queue.add(nxt);
                }
            }
            cnt++;
        }
        Collections.sort(nums);
        if (N >= 1023) System.out.println(-1);
        else System.out.println(nums.get(N));
    }

}

 

 

코드 2. 비트마스킹

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

public class Main {

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

        for (int i = 1; i < 1024; i++) {
            nums.add(convert(i));
        }

        Collections.sort(nums);
        if (N >= 1023) System.out.println(-1);
        else System.out.println(nums.get(N));
    }


    static long convert(int mask) {
        long ret = 0;
        int cnt = 0;
        for (int i = 0; i < 10; i++) {
            if ((mask & (1<<i)) != 0) {
                ret += (i * (long) Math.pow(10, cnt++));
            }
        }
        return ret;
    }
}