큰수 만들기

 

 

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        int next = 0;
        for (int i = 0; i < number.length() - k; i++) {
            int max = 0;
            for (int j = idx; j <= i + k; j++) {
                int current = number.charAt(j) - '0';
                if (max < current) {
                    max = current;
                    next = j;
                }
            }
            sb.append(max);
            idx = next + 1;
        }
        return sb.toString();
    }
}

 

아이디어

주어진 숫자에서 k개의 숫자를 제거하고 남길 수 있는 가장 큰 숫자를 구하려면, 가장 큰 숫자를 앞쪽에 배치하는 방식으로 해결할 수 있습니다. 이를 위해, 숫자를 왼쪽에서부터 탐색하며 남길 자릿수에 맞춰 매번 남은 범위 내에서 가장 큰 숫자를 선택하는 전략을 사용합니다.

 

처음엔 조합으로 모든 경우의 수를 내고 정렬로 뽑으려했지만 많은 시간이 걸려 터질거 같아 그리디로 풀었습니다.

 

코드 실행 (number = "1924", k = 2인 경우)

1. 초기 상태:
   • number = "1924", k = 2
   • 우리가 남길 숫자의 자릿수는 number.length() - k = 4 - 2 = 2자리입니다.
   • 즉, 두 자리 숫자를 만들기 위해 두 번 반복하면서 가장 큰 숫자를 선택합니다.
2. 첫 번째 선택 (첫 번째 자리 찾기):
   • i = 0, 즉 첫 번째 자리를 고르기 시작합니다.
   • 남겨야 하는 두 자리를 만들려면, 첫 번째 숫자는 처음부터 최대 범위까지 탐색할 수 있습니다. 탐색 범위는 number에서 idx = 0부터 i + k = 0 + 2 = 2까지입니다. 즉, "192"에서 가장 큰 숫자를 선택해야 합니다.
   • 탐색 범위: 192
     • j = 0: 숫자 1
     • j = 1: 숫자 9 (현재 가장 큼)
     • j = 2: 숫자 2 (9보다 작음)
   • 탐색 결과: 이 범위에서 가장 큰 숫자는 9입니다. 따라서 첫 번째 자리는 9가 됩니다.
   • next = 1 (숫자 9의 인덱스), 이제 idx를 next + 1 = 2로 업데이트합니다.
   • sb.append(9) → 현재 결과: "9"
3. 두 번째 선택 (두 번째 자리 찾기):
   • 이제 두 번째 숫자를 선택해야 합니다.
   • 남겨야 할 자릿수는 두 자리 중 하나가 남았습니다. 다음 탐색 범위는 idx = 2부터 시작하여 남은 숫자들을 살펴봅니다. 범위는 number에서 idx = 2부터 i + k = 1 + 2 = 3까지입니다. 즉, "24"에서 가장 큰 숫자를 선택해야 합니다.
   • 탐색 범위: 24
     • j = 2: 숫자 2
     • j = 3: 숫자 4 (현재 가장 큼)
   • 탐색 결과: 이 범위에서 가장 큰 숫자는 4입니다.
   • next = 3 (숫자 4의 인덱스), idx는 이제 next + 1 = 4로 더 이상 탐색할 필요가 없습니다.
   • sb.append(4) → 최종 결과: "94"
4. 결과 반환:
   • sb.toString()을 호출하면 최종적으로 “94”가 반환됩니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42883