[탐욕법] 큰 수 만들기 (JAVA)

# 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

---

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

입출력 예

number k return

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

# 정답 코드

public static String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(number);

        int cnt = 0;

        while (cnt != k) {
            int deleteIdx = 0;
            boolean flag = false; //앞 숫자가 뒤 숫자보다 작은 경우 true

            for (int i = 0; i < answer.length() - 1; i++) {
                if (answer.charAt(i) == '9') {
                    i++;
                }
                if (answer.charAt(i) < answer.charAt(i+1)) {
                    deleteIdx = i;
                    flag = true;
                    break;
                }
            }

            if (flag) {
                answer.deleteCharAt(deleteIdx);
            }
            else {
                answer.deleteCharAt(answer.length()-1);
            }

            cnt++;
        }

        return answer.toString();
    }

 

테스트케이스에서 시간 초과가 떠서 걸리는 시간을 줄이기 위해 StringBuilder를 사용했다.

 

cnt로 삭제한 글자 수를 센다.

k 만큼 삭제할 때까지 while문을 반복한다.

 

글자를 삭제하여 가장 큰 수를 만들기 위해서는 앞 숫자가 뒤 숫자보다 작은 경우 제거하면 된다.

삭제할 인덱스를 저장할 deleteIdx를 사용한다.

 

만약 "4321"과 같이 앞 숫자가 뒤 숫자보다 작은 경우가 없다면, 가장 작은 수를 제거하면 된다.

이러한 경우에 가장 작은 숫자는 맨 뒤 숫자이다.

따라서 맨 뒤 숫자를 제거하면 된다.

이런 경우를 확인하기 위해 flag를 사용하였다.

 

for문을 사용하여 기준을 바꿔가면서 각 숫자를 비교한다.

flag가 true가 되면 answer의 deleteIdx 위치를 제거한다.

false라면 answer에서 마지막 위치를 제거한다.

 

만약 현재 숫자가 '9'이면 뒤 숫자와 비교할 필요가 없다.

따라서 '9'인 경우 패스해주었다.

 

# 다른 풀이 1

    public static int max = 0;

    public static String solution(String number, int k) {
        char[] word = new char[number.length()];
        for (int i = 0; i < number.length(); i++) {
            word[i] = number.charAt(i);
        }

        boolean[] selected = new boolean[number.length()];

        combination(word, selected, 0, word.length, number.length()-k);

        return String.valueOf(max);
    }

    //숫자 배열, 선택 체크 배열, 현재 위치, 숫자 배열 길이, 고를 개수
    public static void combination(char[] word, boolean[] selected, int depth, int n, int r) {
        if (r == 0) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < word.length; i++) {
                if (selected[i]) {
                    sb.append(word[i]);
                }
            }

            if (max < Integer.parseInt(sb.toString())) {
                max = Integer.parseInt(sb.toString());
            }

            return;
        }

        if (depth == n) {
            return;
        }

        //word[depth]를 선택한 경우
        selected[depth] = true;
        combination(word, selected, depth + 1, n, r-1);

        //word[depth]를 선택하지 않은 경우
        selected[depth] = false;
        combination(word, selected, depth + 1, n, r);
    }

 

처음 생각난 방법은 조합을 이용하는 것이었다.

만들 수 있는 모든 숫자를 구하여 그 중에서 가장 큰 수를 리턴한다.

정답은 확실하게 구할 수 있지만 재귀 함수를 너무 많이 돌아 대부분의 테스트케이스에서 런타임 에러가 떴다.