[백준] 18511번: 큰 수 구성하기 (Java)

1. 문제설명

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 문제이다.

ex) N=657이고, K={1, 5, 7}일 때 답은 577

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

=> 재귀함수를 이용해 모든 가능한 숫자를 조합하여, (완전탐색)
N보다 작거나 같은 가장 큰 수를 찾는다.

• K의 원소를 배열에 저장하고, 오름차순 정렬한다.
• 재귀를 사용해서 주어진 원소를 조합해 가능한 모든 수를 만든다.
  • 만들어진 수가 n보다 크면 종료한다.
  • 만들어진 수가 n보다 작거나 같은 경우 중 최대값을 찾는다.
  • 배열을 역순으로 탐색한다. (큰 수부터 만들기 위해)

 

3. 최종 코드

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

public class Main {
    static int n, k;
    static int[] num;
    static int result;

    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());
        k = Integer.parseInt(st.nextToken());
        num = new int[k];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<k; i++) {
            // 입력받은 원소를 배열에 저장
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num); // 원소를 오름차순 정렬
        find(0); // 재귀 함수로 탐색
        System.out.println(result);
    }

    static void find(int cur) {
        // cur: 현재 만들어진 수
        if(cur > n) return; // cur이 n보다 크면 탐색 종료
        if(result < cur) result = cur; // cur이 결과값보다 크면 결과값 갱신

        for(int i=k-1; i>=0; i--) { // 큰 수 부터 탐색하도록 배열 역순으로 탐색
            find(cur*10 + num[i]); // 현재 수에 새로운 숫자를 붙여 재귀 호출
        }
    }
}

 

4. 시간복잡도

• K개의 원소 정렬: $O(K log K)$
• 재귀 함수: d를 N의 자릿수라고 할 때, $O(K^d)$

따라서 전체 시간복잡도는 $O(K log K + K^d)$ 이다.

 

5. 느낀점

입력받은 원소로 어떻게 모든 가능한 조합을 만들지 떠오르지 않아서 다른 사람의 풀이를 찾아보게 되었다. 

처음엔 쉬운 문제라고 생각했지만 막상 접근 방식을 생각해내지 못해서 속상했다..