백준 2812번 - 크게 만들기

문제

백준 2812번 - 크게 만들기

아이디어

• 순서를 유지하면서 큰 수가 최대한 앞에 위치하도록 해야한다.
• 스택을 사용하여 스택에 한 자리씩 push 한다.
• 현재 스택에 넣어야 할 숫자가 스택에 마지막에 넣은 숫자보다 크다면 k번 동안 스택에서 pop 한다.
• 이후 스택에 남아 있는 숫자를 앞에서부터 차례대로 빼면 정답이 된다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class BJ_2812 {
    public static void main(String[] args) throws IOException {

        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> stack = new ArrayDeque<>();

        String s = br.readLine();

        for (int i = 0; i < n; i++) {
            int num = s.charAt(i) - '0';

            while (!stack.isEmpty() && stack.peek() < num && 0 < k) {
                stack.pop();
                k--;
            }

            stack.push(num);
        }

        while (0 < k) {
            stack.pop();
            k--;
        }

        StringBuilder sb = new StringBuilder();

        while (!stack.isEmpty()) {
            sb.append(stack.pollLast());
        }
        
        System.out.println(sb);
    }
}