[백준 2812] 크게 만들기 (JAVA)

문제

https://www.acmicpc.net/problem/2812

풀이

스택을 이용하여 해결할 수 있습니다. 현재 스택에 들어있는 값이 들어올 수 보다 크거나 같으면 그냥 push하고 작으면 pop을 하는 방식으로 해결할 수 있습니다.

삭제 카운트 : 3
숫자 : 1231234
Stack []

1. 스택이 비어있으므로 바로 push
   Stack [1]
   count : 3

2. 2가 1보다 크므로 1를 제거 후 push (삭제카운트 -1)
   Stack [2]
   count : 2

3. 3이 2보다 크므로 2를 제거 후 push (삭제카운트 -1)
   Stack [3]
   count : 1

4. 1이 3보다 작으므로 그냥 push
   Stack [3, 1]
   count : 1

5. 2가 1보다 크므로 1를 제거 후 push (삭제카운드 -1)
   Stack [3, 2]
   count : 0

6. count가 0이므로 나머지 출력
   answer : 3234

코드

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        String input = br.readLine();

        Stack stack = new Stack(N);
        int count = 0;
        for (int i = 0; i < N; i++) {
            int num = input.charAt(i) - '0';

            if (!stack.isEmpty()) {
                while (!stack.isEmpty() && count < K) {
                    if (stack.peek() < num) {
                        stack.pop();
                        count++;
                    } else {
                        break;
                    }
                }
            }

            stack.push(num);

            if (count == K) {
                sb.append(input.substring(i+1));
                break;
            }
        }

        while (!stack.isEmpty()) {
            int num = stack.pop();
            if (count < K) {
                count++;
                continue;
            }
            sb.insert(0, num);
        }

        System.out.println(sb);

        br.close();
    }

    public static class Stack {
        int[] arr;
        int idx;

        public Stack(int size) {
            this.arr = new int[size];
        }

        public void push(int num) {
            arr[idx++] = num;
        }

        public boolean isEmpty() {
            return idx == 0;
        }

        public int peek() {
            return arr[idx -1];
        }

        public int pop() {
            return arr[--idx];
        }
    }
}