[프로그래머스 / 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의 자릿수 미만인 자연수입니다.

 

정답 설명

항상 문제를 풀기 전에 이 문제를 풀기 위한 규칙을 찾을 수 있는지를 먼저 고민해 봅시다.

이번 문제의 경우, 제거 할 숫자를 선택하는 규칙이 존재하는지, 또는 주어진 수에서 k개의 수를 제외한 이후의 가장 큰 숫자를 구하는 규칙이 있는지 등을 고민 해 볼 수 있을 것입니다.

 

주어진 n개의 숫자를 이용해 가장 큰 수를 만드는 방법을 먼저 생각해 봅시다. 이는 간단합니다. 주어진 숫자들을 모두 내림차순으로 배열한 수가 만들 수 있는 최댓값입니다. 

 

이번 문제 역시 비슷합니다. 다만, 이번 문제에서는 각 자리의 숫자들의 순서를 변경할 수 없음에 주의합시다.

우리의 목표는 앞자리에 최대한 큰 수를 배치하는 것입니다.

 

다음의 순서로 k개의 수를 제외시킬 수 있습니다.

1. 0번째 순서를 제외한 n번째의 수에 대해
   1. n-1번째 수가 n보다 작다면 n-1번째 수를 제외시킵니다.
   2. n-1번째 수가 n보다 크거나 같다면 n+1번째 수에 대해서 같은 단계를 수행합니다.
2. 해당 수를 끝까지 확인했음에도 제외시켜야 하는 수가 k개 남아 있다면, 뒤에서부터 k개의 수를 제외시킵니다.

 

소스 코드

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder(number);
        
        int check = 1;
        while(check < answer.length() && k > 0){
            if(check != 0){
                if(answer.charAt(check - 1) < answer.charAt(check)){
                    check--;
                    answer.deleteCharAt(check);
                    k--;
                    continue;
                }
            }
            check++;            
        }
        
        return answer.substring(0, answer.length() - k).toString();
    }
}