[프로그래머스/알고리즘 고득점 Kit] Greedy

[sieunnnn]

프로그래머스 알고리즘 고득점 Kit Greedy 문제풀이 입니다.

[sieunnnn]

큰 수 만들기

처음에는 아래와 같이 조합으로 접근하였습니다.

import java.util.*;

class Solution {
    static String answer = "";
    static String[] numbers;
    static boolean[] visited;
    static String max = "0";
    
    public String solution(String number, int k) {
        numbers = number.split("");
        visited = new boolean[numbers.length];
        combination(0, numbers.length, numbers.length - k);
        
        return max;
    }
    
    public static void combination(int depth, int n, int r) {
        if (r == 0) {
            StringBuilder temp = new StringBuilder();
            for (int i = 0; i < visited.length; i ++) {
                if (visited[i]) {
                    temp.append(numbers[i]);
                }
            }
            if (temp.toString().compareTo(max) > 0) {
                max = temp.toString();
            }
            return;
        }
        
        for (int i = depth; i < n; i++) {
            visited[i] = true;
            combination(i + 1, n, r - 1);
            visited[i] = false;
        }
    }
}

하지만 수의 범위가 100만을 넘어가기에 모든 조합을 찾기란 매우 비효율적 이기에 스택 자료구조를 사용하여 문제를 풀었습니다.
(수의 범위 체크하는 습관을 들여야 하는데 말이죵...)