[백준 - 2812] 골드5 -크게 만들기

www.acmicpc.net/problem/2812

2812번: 크게 만들기

1. 유형

그리디

 

2. 풀이

스텍에 순차적으로 넣으면서 시작한다. peek값보다 지금 넣는 값이 더 크다면 더 큰 값이 나올 때까지 

 

계속 pop을 한다

 

3. 코드

package 그리디;

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

public class back_2812크게만들기 {
	public static void main(String[] args) throws IOException {
		BufferedReader	in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int n = Integer.valueOf(st.nextToken());
		int m = Integer.valueOf(st.nextToken());
		String str = in.readLine();
		
		int num = m;
		Stack<Character> stack = new Stack<>();
		stack.push(str.charAt(0));
		for (int i = 1; i < n; i++) {
			while(num > 0 && !stack.isEmpty() && stack.peek() < str.charAt(i)) {
				stack.pop();
				num--;
			}
			if(stack.size()!=(n-m))
				stack.push(str.charAt(i));
		}
		ArrayList<Character> list  = new ArrayList<>();
		while(!stack.isEmpty()) {
			list.add(stack.pop());
		}
		for (int i = list.size()-1; i>=0; i--) {
			System.out.print(list.get(i));
		}
	}
}

 

현재 들어있는 값중에서 비교값보다 더 큰 값이 나올 때까지 pop을 한다

while(num > 0 && !stack.isEmpty() && stack.peek() < str.charAt(i)) {
  stack.pop();
  num--;
}