백준 2812 자바(java) 크게 만들기

문제

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

입력

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

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

출력

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

 

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

public class Main {
	static int[] arr;
	static int count = 0;
	static Stack<Integer> stack = new Stack<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
		arr = new int[n];
		String[] str = br.readLine().split("");
		for(int i = 0; i<str.length; i++) {
			arr[i] = Integer.parseInt(str[i]);
		}
		for(int i = 0; i<arr.length; i++) {
			while(count < k && !stack.isEmpty() && stack.peek()<arr[i]) {
				stack.pop();
				count++;
			}
			stack.push(arr[i]);
		}
		for(int i = 0; i<n-k; i++) {
			System.out.print(stack.elementAt(i));
		}
	}
}

풀이

문제를 쉽게 생각해서 sort를 한다고 생각했지만 주어진 숫자들의 순서가 바뀌면 안된다.

스택을 이용하여 peek()와 조사하는 arr[i]의 인덱스를 비교 후 peek()가 커질때 or 스택이 빌때까지 pop()을 해준 후 만약 원하는 자릿수 만큼의 숫자가 남으면 계속 push() 해줘야 한다.

count<k 가 없을 경우의 반례

6 2

436436

answer : 6436

output : 66 + indexOutOfBound 에러