[백준][JAVA] BOJ 2812 크게 만들기

문제 읽기🤔

---

문제

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

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

 

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

예제 입력 3

10 4
4177252841

예제 출력 3

775841

 

 

문제 풀이📝

---

제일 먼저 떠올랐었던 풀이 방법은 조합이었다.

숫자를 k개 뽑을 수 있는 모든 경우를 고려하면 된다.

결과는 시간초과였지만...

 

조금 더 그리디스럽게 풀어보려고 노력했다.

 

큰 수란, 가장 큰 자릿수의 숫자가 클 수록 큰 수이다.

그래서 맨 앞부터 순회하면서 현재 숫자를 다음 숫자와 비교하고, 작은 수를 지워가면서 큰 수를 만들려고 했다.

그러나 틀렸습니다의 연속...

 

너무 안 풀려서 멘붕이었는데, 알고리즘 고수님이 힌트를 흘리고 가주셔서 바로 풀었다.

현재의 숫자와 이전의 숫자들을 비교해야 올바른 정답을 도출할 수 있었다.

나는 단순히 현재, 다음 숫자만을 비교하여 답이 보이지 않았던 것이었다.

 

이전 숫자들을 저장하기 위해서 스택 자료구조를 사용하였다.

숫자들을 순회하면서,

1) 스택의 peek값보다 작은 숫자를 만났다면 해당 숫자를 스택에 push 해주었다.

2) 스택의 peek값보다 큰 숫자를 만났다면 스택을 pop하고 현재 숫자를 가지고 1)부터 비교 연산을 반복해준다.

3) 순회가 끝났지만, 숫자를 지울 수 있는 k번의 기회를 모두 사용하지 못했다면 남은 기회만큼 스택의 뒤에서 pop한다.

4) 스택에 담긴 값이 만들 수 있는 가장 큰 수이고 이를 출력한다.

스택에 넣은 값들을 확인해보면 스택의 peek에 멀 수록 큰 수이고, 가까울 수록 작은 수 임을 알 수 있다.

 

 

구현🛠

---

package baekjoon;

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

public class Main_2812 {

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

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String[] inputs = br.readLine().split("");

        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i < inputs.length; i++){
        	
            // 현재 입력받은 숫자
            int cur = Integer.parseInt(inputs[i]);

            while(true){
				// 스택이 비어있거나, 더 이상 수를 지울 수 없다면
                if (stk.isEmpty() || k <= 0) break;
                
                // 스택의 peek()와 현재 숫자 비교
                // 이전 숫자가 더 작다면 -> 이전 숫자를 지운다
                else if (stk.peek() < cur) {
                    stk.pop();
                    k--;
                }
                // 이전 숫자가 더 크다면 -> 아무것도 하지 않는다
                else break; 
            }
            // 현재 숫자를 이어붙인다.
            stk.push(cur);
        }

        while(k > 0){
            stk.pop();
            k--;
        }

        StringBuilder sb = new StringBuilder();
        while (!stk.isEmpty()) {
            sb.append(stk.pop());
        }
        System.out.println(sb);
    }
}

 

 

실행결과✅

---