[자바]백준 2812번 크게 만들기 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 알고리즘이란!?

Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

문제

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

입력

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

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

출력

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

 

 

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 스택

 

문제 설명

문제가 간단하니 pass

 

해설

이 문제는 그리디 알고리즘(순서대로)과 stack을 사용하면 된다.

 

N - 자리수

K - 지워 줘야 하는 수

 

1. 숫자 중에 앞자리부터 stack에 넣어주기
2. 넣어줄 때 K만큼 숫자를 빼지 않았으면, 이미 넣은 숫자들이 자기보다 작은 숫자들을 꺼내기

 

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        String s = br.readLine();
        
        Stack<Character> stack = new Stack<>();
        
        int minusCnt = 0;
        for (int i = 0; i < s.length(); i++) {
            while(!stack.isEmpty() && minusCnt < K && stack.peek() < s.charAt(i)) {
                stack.pop();
                minusCnt++;
            }
            
            if (stack.size() < N - K) {
                stack.add(s.charAt(i));
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < stack.size(); i++) {
            sb.append(stack.get(i));
        }
        
        bw.write(sb + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}