프로그래머스 큰 수 만들기(자바) - 탐욕법 Greedy

문제 설명

어떤 숫자에서 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"

---

풀이 :

첫번째 숫자가 클수록 더 큰 수이기 때문에 만약 3자리 수를 return 해야 한다면 끝에 2개의 숫자를 남겨두고 그 앞의 숫자들 중 가장 큰 수를 찾도록 했다.

예를 들어 1231234에서 k가 3이면 4자리 숫자를 return 해야 하는데 이 때 맨 끝에 234 숫자를 제외한 1231 중에서 가장 큰 수 인 3을 찾고, 그 후 이제 숫자 3자리를 채우면 되므로 맨 끝에 34를 남겨둔 후 3보다 뒤에 있는 12 중 큰 수 인 2를 찾고, 그 후 이제 숫자 두 자리를 채우면 되므로 맨 끝에 4를 남겨두고 2보다 뒤에 있는 수는 3 뿐이므로 3을 찾고, 그 후 나머지는 4밖에 없으므로 4를 넣어준다.

 

이를 간단히 정리하면

내가 만들어야 할 숫자의 자릿수는 h = number.length()-k 이다.

1. number[0] 부터 number[마지막 인덱스 - (h-1)] , 즉 인덱스 0부터 k까지의 수 중 가장 큰 수를 고른 후 그 수를 answer에 추가시킨 후 그 인덱스를 i라 하자.

(마지막 인덱스 - (h-1) = number.length - 1 - (number.length - k - 1)) = k 이다.)

2. number[i+1] ~ number[k++] 중 가장 큰 수를 고른 후 i = 가장 큰 수의 인덱스.

3. number[i+1]  ~ number[k++] 중 가장 큰 수 고른 후 i = 가장 큰 수의 인덱스. 

...

 

즉 2번 과정을 k가 number.length()-1 즉, 마지막 인덱스가 될 때까지 반복한다.

 

* 주의해야 할 점은 answer을 String 형태로 두고 거기에 큰 수를 찾을 때마다 넣어주게 되면 시간초과가 발생하므로 StringBuilder를 사용해서 추가해줘야 한다!!

 

아래에서 index를 -1로 초기화시킨 이유는 처음 for문을 돌 때 i가 0부터 시작해야하기 때문이다.

 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        //String answer = "";
        StringBuilder answer = new StringBuilder();
        int max;
        int index = -1;
        while (k <= number.length() - 1) {
            max = 0;
            for (int i = index+1; i <= k; i++) {
                if (number.charAt(i)-'0' > max) {
                    max = number.charAt(i)-'0';
                    index = i;
                }
            }
            answer.append(max);
            k++;  
        }
        return answer.toString();
    }
}