백준 2812번: 크게 만들기 (Java)

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

2812번: 크게 만들기

문제

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

입력

 

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

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

출력

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

 

---

 

풀이

1. 풀이 아이디어

그리디하게, 맨 앞의 숫자와 그 다음에 올 숫자를 비교하여 앞의 숫자가 다음의 올 숫자보다 작다면 해당 숫자를 제외하는 것이 가장 커진다. 이렇게 끝까지 체크하면서, 도중에 K개를 모두 제거했다면 남은 숫자는 그대로 사용하면 되고, 반대로 K개를 모두 제거하지 못했다면 뒤에서부터 K개를 제거할 때까지 빼주면 된다.

'맨 앞 두 원소만 비교하여 제거하는 것이 가장 효율적이다'와 'K개를 모두 제거하지 못한 상황에서는 뒤에서부터 제거하면 된다', 이 두 명제에 대한 증명이 필요하다. 각각의 경우마다, '그리디한 접근'과 '다른 접근'으로 만들어지는 숫자를 앞자리부터 비교하여 '그리디한 접근으로 구한 수' >= max('다른 접근으로 구할 수 있는 수의 집합')임을 보이면 된다. 수식은 생략.

 

2. 구현

다만, 위 아이디어를 string에서 쌩으로 구현하면 O(N^2) 풀이가 나와 시간 초과가 뜰 것이다. 문제 풀이의 주요 아이디어인, '맨 앞의 값만 비교하는 연산'을 구현하기에는 스택이 가장 효율적이다. 하지만, 스택을 쓰면 조립할 때 한번 거꾸로 뒤집어야하므로 양쪽으로 다 넣고 뺄 수 있는 덱을 사용하면 더 좋다.

 

그리디한 풀이 방법 + 이를 구현하는 적절한 자료구조를 생각해야하는 문제이다. 배움을 얻기에 좋은 문제인 듯?

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        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 str = br.readLine();
        Deque<Integer> deque = new ArrayDeque<Integer>();
 
    // 맨 앞 자리부터, 앞 자리에 현재 수보다 작은 값이 있다면 제거함
        for (int i = 0; i < N; i++) {
            int num = str.charAt(i)-'0';
      // K개를 이미 다 제거했을 경우
            if (K == 0) {
                deque.offerLast(num);
                continue;
            }
      // 비어있는 경우
            if (deque.isEmpty()) deque.offerLast(num);
            else {
        // 앞 자리가 현재 수보다 작은 경우
                while (!deque.isEmpty() && deque.peekLast() < num && K > 0) {
                    deque.pollLast();
                    K--;
                }
                deque.offerLast(num);
            }
        }
        
    // K개가 없어지지 않았다면, 맨 뒤에서부터 수를 제거함
        while (K > 0) {
            deque.pollLast();
            K--;
        }
        
        while (!deque.isEmpty()) {
            sb.append(deque.pollFirst()+"");
        }
        System.out.println(sb.toString());
    }
 
}