[Boj] S1 2812 크게 만들기

---

2812 크게 만들기

 

---

 

문제링크

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

 

---

 

 

한시간동안 풀었는데 못 풀었다..

 

처음엔 완탐으로 풀까 했지만 N, K가 최대 500,000까지 들어올 수 있어서, 다른 방식으로 접근했다.

단순히 greedy하게 작은 수부터 지워나갔다. 하지만 런타임 에러, 틀렸습니다 등 골고루 오답이 나왔다.

그리고 결국 못품.

 

스터디원들 중 단 한명만 풀었다.

그 친구의 코드를 리뷰한 다음, 다시 풀었다.

 

1) Stack에 input값을 순서대로 넣는다.

2) 들어갈 input값보다 peek값이 작으면 pop ( input보다 큰 수가 나올 때 까지 )

3) pop할때마다 count증가하면서, count가 K가 되면 다 뺀 것

 

이게 큰 틀이었다. 쉽게 말해서, 큰 수가 작은 수를 다 밀어내고 스택에 들어가는 느낌.

 

세세하게 신경써줘야 할 부분은,

1) Stack에 input을 다 넣지 않았을 때 count가 K가 된 경우

즉, 아직 넣을 input이 남아 있는 데, 숫자를 다 빼버린 경우.

이 경우엔 남은 input을 전부 Stack에 push해준다.

ex)

7 2

3911211

 

2) Stack에 input을 다 넣었는데 count가 K가 되지 않은 경우

즉, input이 빼야될 조건에 해당하지 않는 숫자로 이루어졌을 때.

이 경우엔 남은 count가 K가 될 때까지 pop해준다.

ex)

7 2

9111111

 

 

▼

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main_S1_2812_크게만들기 {
 
    static int N, K, max;
    static char[] num, sort;
    static char[] result;
    static Stack<Character> stack;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        K = Integer.parseInt(str[1]);
        num = new char[N];
        stack = new Stack<Character>();
        num = br.readLine().toCharArray();
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (count == K) {
                // input값 전부 push
                stack.push(num[i]);
            } else {
                while (!stack.isEmpty() && stack.peek() < num[i] && count < K) {
                    stack.pop();
                    count++;
                }
                stack.push(num[i]);
            }
        }
        
        //덜 뺐으면 남은 count만큼 빼주기
        for (; count < K; count++)
            stack.pop();
 
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty())
            sb.append(stack.pop());
        sb.reverse();
        System.out.println(sb.toString());
    }
 
}