[백준 - 2812번] 크게 만들기 - Java

문제 링크

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

문제

알고리즘: 그리디, 스택
티어: 골드 3

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

풀이

N자리 숫자 중 K개를 지워서 가장 큰 수를 구하야 된다.

가장 큰 수는 앞 자릿수가 큰 수이다.

앞 자릿수를 바꿀 수 있으면 최대한 지워줘야 한다.

이때 스택을 이용하면 된다.

차례대로 자릿수를 탐색하면서, 각 자릿수를 스택에 넣어주는데
peek()를 통해 현재 넣는 값보다 작으면서, K != 0이 아니라면 pop()을 해준다.
그리고 조건에 부합하지 않으면 그때 값을 넣어주면 된다.

여기서 pop()을 해주는 이유는 앞에서 말했듯이 앞 자릿수를 바꾸기 위한 과정이다. 그래서 K가 충분하다면, 맨 앞 자릿수 값이 바뀔 것이고, 그렇지 않다면 되는 선에서 가장 큰 값이 되게끔 값이 바뀔 것이다.

예를 들어
10 4
4177252841일 때

자릿수 순서대로 탐색한다.

1. stack -> 4, k=4;
2. stack -> 4 1, k=4;
3. stack -> 7, (7은 1보다 크고, 4보다 크다 그렇기 때문에 stack에는 7만 남음) k = 2;
4. stack -> 7 7, k=2;
5. stack -> 7 7 2, k=2;
6. stack -> 7 7 5, k=3;
7. stack -> 7 7 5 2, k=3;
8. stack -> 7 7 5 8, k=4;
   ...

그래서 답은 775841이 된다.

시간 복잡도는 O(N)이다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N,K;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        int len = N - K;
        String strNum = br.readLine();
        int cursor = 1;
        Stack<Integer> stack = new Stack<>();
        stack.push(strNum.charAt(0) - '0');
        while(cursor < N) {
            int num = strNum.charAt(cursor) - '0';
            if(K != 0) {
                while(!stack.isEmpty() && stack.peek() < num) {
                    stack.pop();
                    K -= 1;
                    if(K == 0) {
                        break;
                    }
                }
            }
            stack.push(num);
            cursor += 1;
        }
        
        StringBuilder sb = new StringBuilder();
        int cout = 0;
        for (Integer element: stack) {
            sb.append(element);
            cout += 1;
            if(cout == len) {
                break;
            }
        }
        System.out.println(sb.toString());
    }
}