[Algorithm] 🔥백준 2812 크게 만들기

0. 문제

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

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

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

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

1. 아이디어

💡 stack 사용
💡 빠질 개수를 조절하는 cnt
💡 stack을 이용하여 안에 들어있는 것이 현재 문자열보다 작고 cnt<k이면 빼냄

2. 핵심 풀이

1. stack을 이용하여 안에 들어있는 것이 현재 문자열보다 작고 cnt<k이면 빼냄

while(cnt<k && !stack.isEmpty() && stack.peek() < c) {
	stack.pop();
	cnt++;
}

3. 코드

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

public class BOJ_2812 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		int n = Integer.parseInt(s[0]);
		int k = Integer.parseInt(s[1]);
		String num = br.readLine().trim();
		
		Stack<Integer> stack = new Stack<>();
		
		int cnt = 0;
		for(int i=0; i<num.length(); i++) {
			int c = num.charAt(i) - '0';
			
			while(cnt<k && !stack.isEmpty() && stack.peek() < c) {
				stack.pop();
				cnt++;
			}
			
			stack.push(c);
		}
		
		for(int i=0; i<n-k; i++) {
			System.out.print(stack.elementAt(i));
		}
		
	}

}

4. 결과

성공✨