[Java] 백준 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

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static BufferedWriter bw;
	private static StringTokenizer st;
	
	private static int N, K;
	private static String num;
	private static Deque<Character> store=new ArrayDeque<>();	// 각 자릿수를 저장할 덱
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		bw=new BufferedWriter(new OutputStreamWriter(System.out));
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		num=br.readLine();	// N자리 숫자를 문자열로 입력받음
		
		int n=0;
		for(int i=0;i<N;i++) {	// N자리 숫자의 각 자릿수
			while(n<K && !store.isEmpty() && store.peekFirst()<num.charAt(i)) {	// 지운 숫자의 개수가 K미만이고, store에 값이 존재하고, store에 존재하는 값이 현재 자리의 숫자보다 작으면, store의 수를 제거함
				store.pollFirst();
				n++;
			}
			store.addFirst(num.charAt(i));	// 현재 자리의 숫자를 store에 저장함
		}

		StringBuilder sb=new StringBuilder();
		while(store.size()>K-n) sb.append(store.pollLast());	// 덱에 존재하는 숫자 중 지운 것을 제외하고 각 숫자들을 이어붙임
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

}

시간 초과, 메모리 초과, 런타임 에러 등 온갖 오답 사유를 만난 문제였습니다.

 

1. 덱에 각 자리의 숫자를 큰 자릿수부터 하나씩 저장하며, 다음 숫자가 더 큰 값이면 이전 값을 삭제합니다.

2. N자리의 숫자를 모두 탐색한 후에 덱에 저장된 각 숫자를 이어붙입니다. 이때 1번에서 K개의 수를 모두 삭제하지 못했을 수 있으므로 K-n개만큼의 숫자만 이어붙입니다.