[백준] 2812번 : 크게 만들기(JAVA)

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

2812번: 크게 만들기

풀이

숫자의 크기와 지워야 할 숫자의 갯수를 입력받고 수를 입력받습니다.

그 수에서 지울 숫자의 갯수만큼 지웠을 경우 최대로 큰 수가 되도록 하는 문제입니다.

전 Stack<Integer>을 이용하여 풀었습니다.

 

자바 특성상 처음 숫자의 크기(문자열의 길이)는 받을 필요없어서 넘겨주고, 지워야할 갯수를 입력받습니다.

다음 문자열의 크기만큼 반복하면서 "스택이 비어있지 않고, 지운 횟수가 지워야할 횟수보다 작고, 스택의 마지막값이 입력받은 값보다 작으면" 스택의 마지막값을 빼주고, 지운 횟수를 증가시켜줍니다.

 

이런식으로 진행하다보면 마지막에 지워지지 않고 추가되어있는 숫자가 있을 수 있으므로, 입력받았던 문자열의 길이 - 지울 횟수 만큼 stack의 값을 순서대로 출력해주면됩니다.

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		st.nextToken();
		int size = Integer.parseInt(st.nextToken());
		
		Stack<Integer> stack = new Stack<>();
		
		String s = br.readLine();
		int count = 0;
		for(int i = 0; i < s.length(); i++) {
			int n = s.charAt(i) - '0';
			
			while(count < size && !stack.isEmpty() && stack.peek() < n) {
				stack.pop();
				count++;
			}
			stack.add(n);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < s.length() - size; i++) {
			sb.append(stack.get(i));
		}
		System.out.print(sb);
	}
}