아이디어

• 핵심 아이디어는 숫자를 지웠을 때 왼쪽이 가장 크도록 하는 것이다..
• 입력은 Doubly linked list를 사용해 받았다.
  • 수의 가장 첫 자리부터 탐색한다.
  • 만약 지울 수 있는 횟수 k가 남아있고, 다음 자리보다 더 작은 숫자라면 지운다.
  • 아니라면 다음 자리로 이동한다.
• $K$번을 모두 사용했다면 그대로 출력하고, 아니면 현재 (남은 숫자의 자릿수 - 남은 k)개 만큼만 앞에서부터 출력한다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, K ,k;
	static Node head, tail, cur;
	static char[] tmp;
	static int n;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = n = Integer.parseInt(tk.nextToken());
		K = k = Integer.parseInt(tk.nextToken());

		tail = head = new Node(Integer.MAX_VALUE, null);
		
		tmp = rd.readLine().toCharArray();
		for (char c: tmp) {
			head = new Node(c - '0', head);
		}
		
		cur = tail.next;
		while (cur.next != null && k > 0) {
			if (cur.n < cur.next.n) {
				cur.prev.next = cur.next;
				cur.next.prev = cur.prev;
				cur = cur.prev;
				
				n--;
				k--;
				if (k == 0) break;
			}
			else cur = cur.next;
		}
		
		cur = tail.next;
		for (int i=0; i<n-k; i++) {
			if (cur == null) break;
			sb.append(cur.n);
			cur = cur.next;
		}
		
		System.out.println(sb);
	}
	
	static class Node {
		int n;
		Node prev, next;
		Node(int n, Node prev) {
			this.n = n;
			this.prev = prev;
			if (prev != null)
				prev.next = this;
		}
	}
}

메모리 및 시간

• 메모리: 24644 KB
• 시간: 840 ms

리뷰

• 이 문제를 stack을 이용해 풀 수 있는 'monotone stack'이라는 테크닉을 알게 됐다.
  • 생각해보면 구조를 스택으로 바꾸고, 입력을 받는 동시에 작업을 처리하면 같은 맥락이 아닐까 싶다.
• NullPointerException 조심 또 조심