어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기

※ 위치는 그대로 하는 것!

시작 index부터 가능한 조합까지의 최대 숫자까지 슬라이싱을 한 후에 최대값을 선택하면 최대값이다. 하지만! 시간 초과…

따라서 스택을 통해 k개의 제거할 수를 선택하는 방법으로 해결할 수 있다.

<aside> 💡 순서를 유지할 수 있는 스택은 슬라이싱에서 유리하다!

</aside>

최대값을 구하기 위해서는 앞에 있는 수가 최대한 커야한다. (자릿수가 최대값)

따라서 stack의 peek와 현재 숫자를 비교하여 큰 수를 push한다.

→ 정답은 stack의 첫 요소부터 순차적으로 가져오는 값이다.

풀이 코드 - 시간 초과

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        int n = number.length() - k; // 선택해야 하는 숫자 개수
        int start_idx = 0;
        int cnt = 0;
        
        while(cnt != n) {
            
            char max = '0'; // start_idx ~ 가능한 조합까지의 최대 숫자 index
            for(int i=start_idx; i<=number.length()-(n-cnt); i++) {
                if(max < number.charAt(i)) {
                    max = number.charAt(i);
                    start_idx = i + 1;
                }
            }
            
            answer += max;
            cnt++;
            
        }
        
        return answer;
    }
}

풀이 코드 - Stack 이용

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        
        Stack<Character> stack = new Stack<>();
        int n = number.length() - k;
        
        for(int i=0; i<number.length(); i++) {
            char current_c = number.charAt(i);
            
            **// 스택의 마지막 숫자보다 현재 숫자가 크면 제거하고 k를 감소 -> 제거 숫자를 선택
            while(!stack.isEmpty() && k>0 && stack.peek() < current_c) {
                stack.pop();
                k--;
            }**
            **stack.push(current_c);**
        }
        
        // 아직 제거해야 할 숫자가 남아 있는 경우 뒤에서 제거
        while(k > 0) {
            stack.pop();
            k--;
        }
        
        // 스택에 남아 있는 숫자로 문자열 만들기
        Character[] numbers = new Character[n];
        for(int i=0; i<n; i++) {
            numbers[n - i - 1] = stack.pop();
        }
        
        for(int i=0; i<n; i++) {
            answer += numbers[i];
        }
        
        return answer;
    }
}