[백준/JAVA] 18311번 : 큰 수 구성하기

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

📌 문제 요약 

 

• N보다 작거나 같은 자연수 중에서, 집합 KKK의 원소로만 구성된 가장 큰 수를 찾아야 한다.
• KKK의 원소는 1부터 9까지의 자연수로 제한된다.
• 항상 NNN보다 작거나 같은 수를 만들 수 있다고 가정한다.

 

 

---

[ 오답 노트 ]
❌ 기존 오답 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 657
        int K = Integer.parseInt(st.nextToken()); // 3
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int answer = 0;

        for(int i = N; i >= 1; i--) {
            // i 숫자를 문자열 변환 후 각 자릿숫자가 1,5,7 로 이루어져있으먄
            for(int j = 0; j < K; j++) {
                if(String.valueOf(i).charAt(j) != st2.nextToken().charAt(0)){
                    break;
                }else {
                    answer = i;
                    break;
                }
            }

        }

        System.out.println(answer);
    }
}

📌 기존 코드의 문제점

1. K의 원소를 제대로 활용하지 못함

 

• st2.nextToken()으로 K의 원소를 매번 하나씩 불러오지만, 이 방식은 K의 모든 원소를 반복적으로 비교해야 하는 문제에 적합하지 않다.
• K의 원소를 배열에 저장해 반복적으로 사용할 수 있어야 한다.

 

 

2. 비효율적인 탐색 방식

 

• N부터 1까지 모든 자연수를 탐색하며 자릿수를 확인하는 방식은 비효율적이다
• 예를 들어, N=10000000일 때 불필요한 탐색이 너무 많아진다

 

 

3. 자릿수 비교의 논리 오류

String.valueOf(i).charAt(j)로 i의 자릿수와 K의 원소를 비교하려 하지만, 이는 자릿수 개수가 다를 경우 오류가 발생한다.

 

 

---

[ 정답 코드 & 올바른 풀이 ]

📌 올바른 풀이

 

1. K의 원소를 제대로 활용하지 못한 문제 해결

K의 원소를 배열에 저장하고, 이를 정렬하여 큰 숫자부터 탐색

arr = new int[K];
        for(int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st2.nextToken());
            // [1,5,7]
        }

 

 

 

2. 깊이 우선 탐색(DFS) 도입

 

• 자연수를 자릿수별로 확장하면서 가능한 조합을 탐색.
• 조건: total이 N보다 작거나 같을 때만 계속 탐색

 if(total > N) return; // 657보다 크면 반환
if(answer < total) answer = total; // 답 계속 갱신

 

 

 

3. 큰 숫자부터 탐색

K의 원소를 내림차순으로 탐색하여 가능한 큰 수를 우선적으로 찾음.

 for(int i = K; i >= 1; i--) { // 큰 숫자부터 탐색
            // 다음 자릿수를 붙임
            dfs(total * 10 + arr[i]);

 

 

---

📌 정답 코드

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

public class Main {
    public static int N, K, answer;
    public static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 657
        K = Integer.parseInt(st.nextToken()); // 3
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        arr = new int[K];
        for(int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st2.nextToken());
            // [1,5,7]
        }

        Arrays.sort(arr); // 오름차순 정렬

        dfs(0);

        System.out.println(answer);
    }

    public static void dfs(int total) {
        if(total > N) return; // 657보다 크면 반환
        if(answer < total) answer = total; // 답 계속 갱신

        for(int i = K-1; i >= 0; i--) { // 큰 숫자부터 탐색
            // 다음 자릿수를 붙임
            dfs(total * 10 + arr[i]);
            // dfs(0)일때,
            // 0 * 10 + arr[2] = 7  --> dfs(7)
            // 0 * 10 + arr[1] = 5  --> dfs(5)
            // 0 * 10 + arr[0] = 1  --> dfs(1)
            // dfs(7)일때,
            // 7 * 10 + arr[2] = 77 --> dfs(77)
            // 7 * 10 + arr[1] = 75 --> dfs(75)
            // 7 * 10 + arr[0] = 71 --> dfs(71)
            // dfs(5)일때,
            // 5 * 10 + arr[2] = 57 --> dfs(57)
            // 5 * 10 + arr[1] = 55 --> dfs(55)
            // 5 * 10 + arr[0] = 51 --> dfs(51)
            // ...
            // dfs(77)일때,
            // 77 * 10 + arr[2] = 777 --> 불가능 dfs 종료
        }

    }
}