[BOJ] 백준 2812번 : 크게 만들기 (JAVA)

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

2812번: 크게 만들기

문제

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

입력

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

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

출력

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

 

풀이

그리디 알고리즘과 자료구조를 사용하여 풀 수 있는 문제였습니다. 저는 자료구조 중에서도 'Deque'를 사용했습니다. 처음에는 스택으로 풀려고 했으나, 상황이 여의치 않아서 스택+큐의 성질을 갖는 데크가 도움이 되었습니다.

전반적인 로직은 다음과 같습니다.

1. 데크가 비어있을 경우 input[i]를 맨 끝에 집어 넣는다.

2. 데크가 비어있지 않을 경우, 데크의 맨 끝 요소와 input[i]에 대해 비교를 한다.

2-1. 데크의 맨 끝 요소가 작을 경우 데크에서 없앤다.

2-2. 2번이 만족하지 않을 경우, 2번 과정을 종료한다.

3. input[i]를 맨 끝에 집어 넣는다.

 

아래 예시를 통해 좀 더 자세히 알아보겠습니다.

 

예시

(1) N = 5, K = 2, input = 89123

처음에는 deque가 비어있으므로 8을 맨 끝에 집어넣습니다.

 

 

그리고 input[1] = 9과 deque에 맨 끝과 비교해 봅시다. deque에 맨 끝은 8이므로 9보다 작습니다. 따라서 deque에서 8을 삭제하고 9를 추가합니다.

 

 

input[2] = 1입니다. deque에 맨 끝인 9보다 작으므로 1을 바로 추가합니다.

 

 

input[3] = 2입니다. deque에 맨 끝은 1이므로 1을 삭제합니다. 삭제 후,  deque에 맨 끝은 9이므로 2보다 큽니다. 따라서 삭제 과정을 종료하고, 2를 추가합니다.

 

 

input[4] = 3입니다. deque에 맨 끝과 비교를 하려고 하였으나, 이미 2번을 지운 상태이므로 삭제 과정을 거치지 않고 바로 3을 추가합니다.

 

 

그림에서 볼 수 있듯이, 답은 923이 됩니다.

 

하지만, K만큼 삭제하기 전에 위에 과정이 끝나는 경우도 있습니다.  아래 예시를 통해 알아봅시다.

 

(2) N = 5, K = 2, input = 55555

숫자가 이렇게 중복되어 나타나는 경우, 삭제하는 과정 없이 단순히 deque에 추가만 된다는 사실을 알 수 있습니다. 따라서 이러한 경우에는 deque.size() - K만큼만 출력을 해 주어야 합니다.

 

아래는 위 풀이와 예제를 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        String input = br.readLine();
 
        char[] arr = input.toCharArray();
        Deque<Character> dq = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            // 데크의 맨 뒤의 값이 arr[i]보다 작으면 삭제한다.
            // 아래 조건을 만족할 때까지 반복.
            while (K > 0 && !dq.isEmpty() && dq.getLast() < arr[i]) {
                dq.removeLast();
                K--;
            }
            dq.addLast(arr[i]);
        }
 
        StringBuilder ans = new StringBuilder();
        // 위 for문에서 K가 0이 되기 전에 끝난 경우를 대비하여
        // dq.size() - K만큼만 출력한다.
        while (dq.size() > K) {
            ans.append(dq.removeFirst());
        }
 
        bw.write(ans.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.