[BOJ 2812] 크게 만들기(Stack, Java)

www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

## 접근방법

---

이 문제는 스택을 이용해서 풀어야 한다. N이 500,000이므로 우선순위큐를 이용한 N * logN 시간복잡도가 걸린다면, 시간초과가 발생할 것이다.

 

 

 

따라서, 선형 탐색이 필요하다. K개를 지워서 가장 큰 수를 만드려면, 앞자리수가 커야 좋다. 값을 비교하고, 가장 큰 수를 만들수 있는 후보들을 저장하는 자료구조가 필요하다.

 

 

 

스택을 사용하면 입력된 순서대로 값의 비교가 가능하므로 자료구조로 스택을 사용할 것이다.

 

 

 

값을 비교할 때는, 스택의 peek 값과 현재 가르키는 값을 비교해야 한다. 

 

 

 

스택포인터가 가르키는 값보다, 현재 값이 크다면 스택에 존재하는 값들은 사용될 필요가 없다. 처음부터 얘기했듯이 앞자리수가 커야 가장 큰 값을 만들 수 있다. 따라서 스택의 pop 연산이 발생한다.

 

 

 

스택포인터가 가르키는 값보다, 현재 값이 작다면 스택에 add 연산을 해주면 된다. 작은 값들은 추후에 큰 값이 등장하지 않는다면, 가장 큰 수를 구성하는 멤버로 사용될 것이므로 add 연산이 필요하다.

 

 

 

주의할 점은 pop 연산이 발생될 때, 탐색이 남은 수들의 개수과 스택의 크기를 더했을 때 N - K 길이의 수를 만들 수 있어야 한다.

 

 

 

탐색이 남은 수들의 개수 + 스택의 크기를 했을 때 N - K 초과가 되어야 한다. N - K 초과가 되어야 하는 이유는 스택의 사이즈는 유동적이고, 탐색이 남은 수들의 개수는 해당 for문의 i가 동일할 때는 고정적이다. 하지만, i가 for문 연산을 통해서 변경되면 스택의 사이즈는 동일한데, 탐색이 남은 수들은 -1이 발생한다. 다음 for문에서 N - K를 절대 만들 수 없게 되므로, 이상이 아닌 초과를 사용해야 한다.

 

 

 

## 해설코드

---

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, K;
    static Stack<Item> stk;
    static String str;
    static String[] sArr;
    static StringBuilder sb = new StringBuilder();
    
    static class Item{
        int idx, val;
        Item(int idx, int val){
            this.idx = idx;
            this.val = val;
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sArr = br.readLine().split(" ");
        
        N = Integer.valueOf(sArr[0]);
        K = Integer.valueOf(sArr[1]);
        
        stk = new Stack<>();
        
        str = br.readLine();
        
        for(int i = 0; i < str.length(); i++){
            int num = Integer.valueOf(str.charAt(i));
            
            if(!stk.isEmpty()){
                while(!stk.isEmpty() && stk.peek().val < num){
                    if(stk.size() + (N - i) > N - K) 
                        stk.pop();
                    else
                        break;
                }
            }
                
            stk.add(new Item(i, num));
        }
        
        while(!stk.isEmpty())
            sb.append(String.valueOf(stk.pop().val - '0'));
        
        sb = sb.reverse();
        bw.write(sb.substring(0, N - K).toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}