백준 2812 (크게 만들기) - java

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

2812번: 크게 만들기

문제 :

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

ex : 1924 에서 2개를 지운다면 94

 

유형 : 그리디 + 자료구조 (스택)

개인적으로 진짜 어려운 문제라고 생각한다 ! 정말 많은 시행착오가 있었던 문제다....

 

접근

• 큰 수라는 개념에 대해 집중해야 한다. 큰 수란 결국 자릿수에 따라 무게가 달라진다는 것이다. 900 이 799보다 큰것처럼 큰 자리에 무조건 큰 수가 와야 한다.
• 결국 m개를 지웠을 때 결과로는 자릿수가 동일할 것이기 때문이다.
• 수를 저장할 자료구조로는 스택을 사용할 것이다. 이전 수들과 비교하여 큰 수를 찾을 때까지 스택을 비워갈 것이다.
• 모든 수를 탐색(반복문)을 수행했을 때 m개 만큼 수를 지우지 못할 수 있다.
  • 여기서가 가장 문제인데 간단하게 앞에서 부터 (n-m) 구하고자 하는 자릿수 만큼만 결과로 만들면 된다.
  • 그 이유는 애초에 수를 m개만큼 지우지 못한 상황에서 뒤의 수는 앞의 수보다 클 수가 없다 !!!!!
  • 이것을 이해하기 어렵다면 직접 그려보는 것을 추천한다.
  • 예시 : 6 , 3 , 773671

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int last = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        last = m;

        char[] arr = br.readLine().toCharArray();
        Stack<Integer> stack = new Stack<>();

        for(int i=0;i<arr.length;i++){

            int cur = arr[i] - '0';

            while(m > 0 && !stack.isEmpty()){
                int tmp = stack.peek();

                if(tmp < cur && m > 0){
                    m--;
                    stack.pop();
                }

                else{
                    break;
                }
            }

            stack.push(cur);
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        sb.reverse();


        System.out.println(sb.substring(0,n-last));

        br.close();
    }
}