[Algorithm] 큰 수 만들기_Greedy

문제 설명

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

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

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

제한 조건

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

입출력 예

number 1924
k 2
return 94

number 1231234
k 3
return 3234

number 4177252841
k 4
return 775841

접근하기

• 처음엔 완전 탐색으로 풀려고 했다. 근데 9999일 경우 아주 최악이다.
• 몇 개의 숫자를 뽑는게 아니라 몇 개의 숫자를 제외한다는 점이 포인트다.👻
• 몇 개의 숫자를 뽑는거라면 순열을 이용할 수 있겠지만, 몇 개를 제외하고 거기서 최대를 구하고 이런 과정을 반복해야 정답에 도달한다.
• 결국, 몇 개를 제외하고 범위를 정하고 거기서 최대를 구하고 바로 그리디 문제다.
• 늘 문제를 푸는 시간보다 문제에 접근하는 방법을 찾는 시간에 더 많은 시간을 쏟는다...물론 중요하지만😖

Code

class Solution {
    public String solution(String number, int k) {
        int pos = 0;
        char max;
        StringBuilder answer = new StringBuilder();
        
        if(number.charAt(0)=='0') return "0";
        
        //len-k 갯수를 뽑기 위한 반복
        for(int i=0; i<number.length()-k; i++){
            max = '0';
            
            //지정 범위 중 최대값을 뽑기 위한 반복
            for(int j=pos; j<=k+i; j++){
                if(max < number.charAt(j)){
                    max = number.charAt(j);
                    pos = j+1;
                }
            }
            
            answer.append(max);
            
        }
        
        return answer.toString();
    }
}

• 연산 속도를 위해 StringBuilder를 사용하였다.
  

• 왜지? 싶다면 String vs StringBuilder vs StringBuffer 이 글을 보자. 🤭