[자바] 백준 2812번: 크게 만들기

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

 

---

앞에 있는 수를 최대한 큰 수로 만들어야한다

스택을 사용한다. 

TOS의 값과 새로 넣을 값을 비교해서, 새 값이 더 작거나 같으면 그대로 push한다.

새 값이 더 크다면, 앞에있는 작은 숫자들을 뺄 수 있는 만큼(k개 제한) pop한다.

 

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

public class P2812 {

	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());

		Stack<Integer> stack = new Stack<>();

		String num = br.readLine();

		for (int i = 0; i < n; i++) {
			int single_num = num.charAt(i) - '0';
			if (stack.isEmpty() || stack.peek() >= single_num) {
				stack.add(single_num);
			} else {
				while (!stack.isEmpty() && k > 0 && stack.peek() < single_num) {
					stack.pop();
					k--;
				}
				stack.add(single_num);
			}
		}

		if (k > 0) {
			while (!stack.isEmpty() && k > 0) {
				stack.pop();
				k--;
			}
		}

		for (int i : stack) {
			System.out.print(i);
		}
	}

}