[PS] 백준 2812번 크게 만들기

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

문제 설명

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하는 문제이다. 이 때, K < N <= 500,000 이고 주어지는 수는 0으로 시작하지 않는다.

문제 풀이

큰 자릿수에 큰 숫자가 오도록 숫자 K개를 지우면 된다(당연하게도). 문제는 K개를 지워야 하고 자리를 바꿀 수는 없다는 사실이다. 그러면 어떻게 지워야 할까? 우선, 큰 자릿수부터 봐야할 것 같다. 그렇다면 큰 자릿수를 고정해놓고 작은 자릿수의 숫자들과 비교하면서 지울 것인가? 답을 구할 수 없다. 예를 들어 3214가 있다고 하자. 1개를 지워야 한다. 그러면 큰 자릿수부터, 3과 2를 비교해서 2가 작으니 2를 지울 것인가? 아니다. 답은 324다. 어떤 숫자는 그 뒤에 있는 숫자와 비교한 후에만 그 숫자를 지울지 말지를 판단할 수 있다.

주목해야 하는 포인트는 큰 자릿수의 숫자부터 보면, 그 숫자를 지워야 하는지 아닌지는 그 시점에서는 알 수 없다는 점이다. 다만, 추후에 알 수는 있으며 추후에 알았을 때 처리해야 하는 순서는 LIFO 순서라는 점이다. 다시말해 판단을 유보한다는 것이다. LIFO 순서이니 우리는 그 데이터를 Stack을 이용해 저장해두면 된다는 것도 알 수 있다.

큰 자릿수부터 본다. 스택이 비어있거나 스택의 top에 있는 숫자보다 보고 있는 숫자가 작다면 push한다. 크다면 pop하고 스택의 top과 비교하는 것을 반복한다. k개를 pop했다면 아직 보지 못한 자릿수를 모두 스택에 push하고 스택의 내용을 역순으로 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int n, k;
    static char[] numStr;
    static ArrayDeque<Integer> stack;

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        numStr = br.readLine().toCharArray();

        stack = new ArrayDeque();

        go();

        StringBuilder sb = new StringBuilder();
        Iterator iter = stack.descendingIterator();
        int cnt = 0;
        // n - k 자리 까지만 출력
        while (cnt < n - k) {
            sb.append(iter.next());
            cnt++;
        }

        System.out.println(sb.toString());
    }

    static void go() {
        int cnt = 0; // 제거한 숫자 갯수

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() < numStr[i] - '0' && cnt < k) {
                stack.pop();
                cnt++;
            }

            stack.push(numStr[i] - '0');
        }
    }
}