백준_2812 크게 만들기 (자바) / 그리디 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Back_2812 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		String tmp = br.readLine();
		Deque<Character> dq = new ArrayDeque<>();
		
		for (int i = 0; i < N; i++) {
			
			while(K>0 && !dq.isEmpty() && dq.getLast() < tmp.charAt(i)) {
				dq.removeLast();
				K--;
			}
			dq.addLast(tmp.charAt(i));
		}
		
		while(dq.size() > K) {
			sb.append(dq.removeFirst());
		}
		System.out.println(sb);
	}
}

 

※ 내 생각

이 문제는 Deque를 이용하면 좀 쉽게 해결할 수 있는 문제입니다.
문제풀이는 기본적으로 그리디 알고리즘을 이용해서 해결을 했습니다.
K>0 인 경우 그리고 데크가 비어 있지 않은 경우 
마지막으로 for문 돌릴 때, i 위치의 숫자와 마지막으로 들어가 있는 숫자를 비교합니다.
만약에 들어가 있는 숫자가 작으면 자릿수가 높은 숫자가 작다는 것을 의미 하기 때문에 제거해줍니다.

출력시에는 K의 갯수만큼 빼야 하기 때문에 사이즈가 K보다 큰 경우만 앞에서 부터 출력을 해주면 됩니다.