프로그래머스 - 큰 수 만들기(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"

문제 풀이 방법

숫자의 길이에서 k개를 뺀 길이는 총 6이 된다.
여기서 확실히 보장되어야하는 자리는 뒷자리 5개를 고정으로 두고 앞에 5자리 중에서 제일 큰 숫자를 선택한다.

제일 큰 숫자를 answer에 값을 넣어 준뒤 큰 자리 인덱스부터 맨 앞까지 필요 없는 숫자이므로 지워준다.

구해야할 6자리 중에 한자리는 확정이 되었으며, 뒷 4자리는 다시 고정해두고 앞 3개의 숫자에서 큰 숫자를 찾는다.

큰 숫자는 다시 answer에 넣어 준뒤 큰숫자 인덱스부터 앞까지 해당 값을 지워준다.
여기서는 앞의 값이 없으므로 큰 숫자 하나만 지워준다.

그다음 뒷 3자리를 다시 고정시키고 앞의 3자리에서 큰 값을 찾는다.

제일 큰 숫자를 answer에 값을 넣어 준뒤 큰 자리 인덱스부터 맨 앞까지 필요 없는 숫자이므로 지워준다.

이것을 끝까지 반복하여 구한다.

여기서 StringBuilder 를 사용한 이유는 String 보다 연산이 빠르기 때문이다.

전체 코드

class Solution {
    public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder("");
        int len = number.length() - k;
        int start = 0;

        while(start < number.length() && answer.length() != len) {
            int leftNum = k + answer.length() + 1;
            int max = 0;
            for (int j = start; j < leftNum; j++) {
                if (max < number.charAt(j) - '0') {
                    max = number.charAt(j) - '0';
                    start = j + 1;
                }
            }
            answer.append(Integer.toString(max));
        }
        return answer.toString();
    }
}