[Coding Test Bookmark] 큰 수 만들기(탐욕법)[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"

 

Java

class Solution {
    public String solution(String number, int k) {
        StringBuilder result = new StringBuilder();
        int length = number.length();
        int remain = length - k;
        for (int i = 0; i < length; i++) {
            char currentDigit = number.charAt(i);
            // 결과에 추가할 문자보다 현재 문자(currentDigit)가 더 크고, 제거할 숫자가 남아 있다면
            while (k > 0 && result.length() > 0 && result.charAt(result.length() - 1) < currentDigit) {
                // 결과의 마지막 문자 제거
                result.deleteCharAt(result.length() - 1);
                // 제거할 숫자 카운트 감소
                k--;
            }
            result.append(currentDigit);
        }
        return result.substring(0, remain);
    }
}

코드 설명

초기 설정

• result는 최종적으로 만들어질 숫자를 저장할 변수.
• length는 문자열의 총 길이.
• remain은 최종적으로 남아야 할 숫자의 길이.

예를 들어, "1924"에서 두 개의 숫자를 제거해야 하므로, 남아야 할 길이는 4 - 2 = 2

문자 처리 루프

• 문자열의 각 문자(currentDigit)를 하나씩 확인

예시:

• i = 0일 때, currentDigit는 '1'
• i = 1일 때, currentDigit는 '9'
• i = 2일 때, currentDigit는 '2'
• i = 3일 때, currentDigit는 '4'

문자 비교 및 삭제

• currentDigit가 result의 마지막 문자보다 클 때, 마지막 문자를 삭제하는 것
• 이렇게 해서 더 큰 숫자를 만들 수 있습니다.
• k는 제거할 숫자의 개수를 세고, result에서 문자를 삭제하면서 k를 감소시킵니다.

예시:

• i = 0, currentDigit = '1': result는 빈 상태이므로 아무 작업도 하지 않음. 결과: "1"
• i = 1, currentDigit = '9': '1'이 '9'보다 작으므로 '1'을 삭제. 결과: "9", k = 1
• i = 2, currentDigit = '2': '9'이 '2'보다 크므로 아무 작업도 하지 않음. 결과: "92"
• i = 3, currentDigit = '4': '2'이 '4'보다 작으므로 '2'을 삭제. 결과: "94", k = 0

결과 문자열 조정

• 최종적으로 result에서 필요한 길이(remain)만큼 잘라서 반환합니다.

예시:

• 최종 결과의 길이는 2이므로, result의 첫 2개의 문자를 반환합니다. 최종 결과는 "94"

전체 코드 실행 결과

• 입력: number = "1924", k = 2
• 출력: "94"