[백준][BOJ-2812][JAVA] 크게 만들기

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

2812번: 크게 만들기

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

public class Main {
	int N,K;
	private void solution() 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());
		
		char[] ch = br.readLine().toCharArray();
		int[] numbers = new int[ch.length];
		
		for(int i=0; i<ch.length; i++) {
			numbers[i] = ch[i] -'0';
		}
		
		Stack<Integer> stack = new Stack<>();
		
		for(int i=0; i<numbers.length; i++) {
			while (K > 0 && !stack.isEmpty() && stack.peek() < numbers[i]) {
                stack.pop();
                K--;
            }
            stack.add(numbers[i]);
		}
		
		//K 만큼 제거
		for(int i=0; i<K; i++) {
			stack.pop();
		}
		
		StringBuilder sb = new StringBuilder();
		int size = stack.size();
		for(int i=0; i<size; i++) {
			sb.append(stack.pop());
		}
		
		System.out.println(sb.reverse().toString());
	}

	public static void main(String[] args) throws IOException{
		new Main().solution();		
	}
}

정리

문제 특성상 현재 숫자의 자리가 앞의 숫자들이 작다면 K의 허용까지 제거시켜주면 된다. 따라서 앞의 숫자들의 정보를 알아야 되기 때문에 스택을 써서 풀면 간단하게 풀린다.

간단하게 예시로 보자!

6 2
391123

위의 예시를 보자 3의 입장에서는 앞의 숫자가 없기에 그대로 스택에 들어간다. 그다음 9는 스택의 탑 값 즉! 3보다 크다 따라서 3은 제거시켜야 된다. ( K 허용선 안에서 반복 )

그리고 K만큼 제거를 다 하게 된다면 그냥 그대로 스택에 넣어준다. 그다음 StringBuilder를 이용해서 출력해주면 된다.

코드에 주석으로 K만큼 제거는 아래의 예시 같은 경우때문에 넣어주었다.

7 3
7654321

위와 같은 예시에는 그대로 7654321이 스택에 들어가게 됨으로 K만큼 스택의 탑을 제거시켜주면 된다.