[백준 2812번] 크게 만들기 (Java 풀이)

백준알고리즘 2812번 : 크게 만들기

 

 

역시 그리디 알고리즘은 어떻게 풀지 구상하는 것이 실마리의 절반 이상을 차지하는 것 같다.

엄청 애먹었지만 풀이 방식을 몇번 뒤엎은 끝에 stack을 이용해서 문제 해결에 성공했다.

처음 풀었을 때는 '지워야 하는 숫자의 갯수를 기억함과 더불어 check가 필요한 남은 숫자도 기억해야 하는게 아닌가?' 라고 생각했다.

이런 생각을 가지고 풀다보니 지워야하는 숫자와, 남은 문자열의 길이를 함께 계산하여 무지막지한 소스가 완성되었고

뻘짓을 4시간가량 반복했다.

결과적으로는 남은 문자열의 길이는 크게 신경쓸 필요 없으며, 판단해야하는 것은 두가지 뿐이다.

1. 지워야 하는 숫자의 개수를 먼저 소진했는가?

2. 지워야 하는 숫자가 아직 남았는가?

이 조건만 check하고 문제를 풀어나가면 어렵지 않게 풀수있다.

여전히 소스는 미덥지 못하여 다른 소스코드를 더 참고해서 다듬어 보려한다.

 

 

풀이 과정

---

1. 문자열을 탐색하면서 stack에 담은 기존 문자가 새 문자보다 작으면, 크거나 같은 문자가 나올
    때까지 pop한뒤 push한다.
2. 1번의 과정을 지워야하는 개수가 0이 되거나 문자열을 모두 탐색할 때까지 반복한다.
3-1. 지워야하는 개수가 0이 먼저되었다면, 나머지 문자열은 모두 push한다.
3-2. 문자열 탐색이 먼저 끝났다면, 기존 push된 문자열에서 남은 지워야하는 개수만큼 pop한다.
4. push된 stack을 역순으로 출력한다.

 

 

 

소스 ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {// No2812 : 크게 만들기

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int len = Integer.parseInt(st.nextToken());
        int minus = Integer.parseInt(st.nextToken());
        String[] str = br.readLine().split("");
        int[] num = new int[str.length];
        for (int i = 0; i < len; i++) {
            num[i] = Integer.parseInt(str[i]);
        }
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int cnt = 0;
        while (minus != 0 && cnt < num.length) {
            int tmp = num[cnt];
            while (!stack.isEmpty() && minus != 0) {
                if (stack.peek() < tmp) {
                    stack.pop();
                    minus--;
                } else {
                    break;
                }
            }
            stack.push(tmp);
            cnt++;

        }
        if (minus == 0 && cnt != num.length) {
            while (cnt < num.length) {
                stack.push(num[cnt]);
                cnt++;
            }
        }
        if (minus != 0) {
            while (minus != 0) {
                stack.pop();
                minus--;
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        System.out.println(sb.reverse());
    }
}