[lv.2] 큰 수 만들기

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

• 문제

  어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
  예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
  문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

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

• 풀이
  1) 문자열의 길이를 n이라 할 때, 만들어야 하는 문자열의 길이는 n-k이다.
  2) 즉, n-k-1만큼의 뒤의 문자열을 남겨두고, 앞에서부터 n-k까지의 가장 큰 값과 인덱스를 구한다.
  3) 이후 남겨야할 뒤의 문자열의 길이를 --하며 앞에서 저장한 인덱스+1부터 차례로 구해가며 반복한다.
  4) 위만 구현할 경우 시간초과가 날 텐데, 만약 비교할 값이 9라면 그 뒤의 값들은 탐색하지 않아도 된다.

• 예시 (4177252841)
  0) max=0, idx=0
  1) 41772 52841 -> max=7, idx=2+1 (이미 넣은 값을 다시 넣을 순 없다.)
  2) 725 2841 -> max=7, idx=3+1
  3) 252 841 -> max=5, idx=5+1
  4) 28 41 -> max=8, idx=7+1
  5) 4 1-> max=4, idx=8+1
  6) 1 -> max=1, idx=9+1
  -> result = 7 7 5 8 4 1

• 코드

import java.util.*;

class Solution {
    public String solution(String num, int k) {
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        int max = 0;
        int n = num.length();
        for(int i=0; i<n-k; i++){
            max = 0;
            for(int j=idx; j<=k+i; j++){
                if(num.charAt(j)=='9'){ // 안 넣으면 시간 초과
                    max = 9;
                    idx = j+1;
                    break;
                }
                if(max<num.charAt(j)-'0'){
                    max = num.charAt(j)-'0';
                    idx = j+1;
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}