백준 2812 크게 만들기 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/2812

2. 코드가 나오기까지 🛠️

1. nums[0]를 stack에 담는다.

2. 이제 nums[1]부터 nums[N-1]까지 순회하며 다음을 반복한다. (지시자 = i)
1. stack의 top보다 num[i]가 더 클 경우 stack.pop()을 한다.
2. 1번을 stack.top >= nums[i]가 될때까지 혹은 pop() 횟수가 K번을 넘지 않을 떄까지 반복한다.
3. 이후 nums[i]를 stack에 넣는다.
4. 만약 pop 횟수가 K번이 되었다면 더 이상 pop은 안되므로 이후의 숫자는 stack의 size()가 N-K가 될 때까지 그냥 집어넣는다.

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

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

// 2812번 크게 만들기
public class Main {
    static int N, K;
    static int [] nums;
    static int [] stack;
    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());
        K = Integer.parseInt(st.nextToken());
        nums = new int [N];
        stack = new int [N-K];
        char [] temp = br.readLine().toCharArray();
        for(int i = 0; i < temp.length; i++){
            nums[i] = temp[i] - '0';
        }        int cnt = 0;
        int top = 0;
        stack[top] = nums[top];
        for(int i = 1 ; i < N; i++){
            int now = nums[i];
            while (cnt < K &&  top >= 0 && stack[top] < now) {
                top--;
                cnt++;
            }            top++;
            if(top >= N-K) break;
            else stack[top] = now;
//            System.out.printf("top=%d, cnt=%d %s\\n", top, cnt, Arrays.toString(stack));
        }
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i < stack.length; i++){
            ans.append(stack[i]);
        }        System.out.printf("%s", ans);
    }}

4. 트러블 슈팅 or 배운 점📝

(1) 아이디어 못 떠올림