[백준] 1174: 줄어드는 수 - JAVA

14 Jun 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

321, 950처럼 왼쪽부터 자리수가 감소할 때 줄어드는 수를 찾는 문제.

줄어드는 수를 저장해놓고 N번째 줄어드는 수를 출력해주었다.

줄어드는 수 중 가장 큰수는 “9876543210”이다. (long 범위)

{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}의 배열을 만들어 놓고 앞에서부터 해당 인덱스를 선택할지 여부를 조합으로 수를 만든다.

만든 수를 list에 넣어 정렬했다.

list를 인덱스로 접근하여 출력하면 문제 끝.

조합을 할 때, 재귀로 접근할 수도 있고, 비트마스킹을 이용할 수 있다.

처음에 재귀로 문제를 풀고, 비트로 하는 방법을 찾아봤다.

---

재귀

메모리: 14500KB

시간: 152ms

언어: Java 11

코드

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

public class Main {
    static int[] digit = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    static List<Long> list;

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

        list = new ArrayList<>();

        makeNum(0, 0);

        Collections.sort(list);

        if (N > list.size()) {
            System.out.println(-1);
        } else {
            System.out.println(list.get(N - 1));
        }

    }

    private static void makeNum(long num, int idx) {

        if (idx == 10) {
            if (!list.contains(num)) {
                list.add(num);
            }
            return;
        }

        // 해당 인덱스를 선택안하고 넘어간다.
        makeNum(num, idx + 1);

        // 해당 인덱스를 선택한 경우 num에 더해준다.
        makeNum(num * 10 + digit[idx], idx + 1);
    }

}

---

비트

메모리: 14300KB

시간: 128ms

언어: Java 11

코드

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

public class Main {
    static int[] digit = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    static List<Long> list;

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

        list = new ArrayList<>();

        makeNum();

        Collections.sort(list);

        if (N > list.size()) {
            System.out.println(-1);
        } else {
            System.out.println(list.get(N - 1));
        }

    }

    private static void makeNum() {
        // 10자리의 모든 경우의 수를 만든다.
        for (int i = 1; i < (1 << 10); i++) {

            long num = 0;
            for (int j = 0; j < 10; j++) {
                // 해당 비트가 1이면 해당 인덱스를 선택했다는 것.
                // num에 더해준다.
                if ((i & (1 << j)) > 0) {
                    num = num * 10 + digit[j];
                }
            }

            list.add(num);
        }
    }

}