[BOJ] 2812. 크게 만들기

스택을 사용하는 그리디 문제였다.

이 문제는 숫자의 앞에서부터 스택에 집어넣으며 순서를 지키며 가장 큰 수를 만드는 문제이다. 즉 다음과 같은 로직을 가진다. 현재 스택에 집어넣어야할 숫자에 대해서 만일 지울 수 있는 횟수가 남아있고, 스택의 top 값이 현재 숫자보다 작다면 스택의 top을 제거하는 것을 반복하고 현재 숫자를 스택에 push해주는 원리이다. 그후 최종적으로 N-K만큼의 길이를 스택의 bottom에서부터 보여주는 방식으로 해결할 수 있다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main_bj_2812_크게만들기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        Deque<Integer> deque = new LinkedList<>();
 
        String input = br.readLine();
 
        int delete = 0;
 
        for (int i = 0; i < input.length(); i++) {
            int next = input.charAt(i) - '0';
 
            while (true) {
                if (deque.isEmpty() || (delete >= K)) {
                    break;
                }
 
                int top = deque.peekLast();
                if (top < next) {        //지울수있는 경우 현재 기준 앞에있는 작은 수를 지울수있는 곳까지 지워주는게 이득
                    deque.removeLast();
                    delete += 1;
                } else {
                    break;
                }
            }
 
            deque.addLast(next);
        }
 
        StringBuilder sb = new StringBuilder();
 
        for (int i = 0; i < N - K; i++) {
            sb.append(deque.removeFirst());
        }
 
        System.out.println(sb.toString());
    }
}