백준 2812번 - 크게 만들기 (Java, Deque + 그리디)

문제

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

문제 접근

• 완전 탐색은 불가능 : N이 최대 50만 → 모든 조합(nCk)을 탐색하는 DFS 방식은 시간 초과 발생
• 그리디 + Deque 사용
  • 앞자리가 클수록 전체 수가 큼
  • 현재 숫자가 이전 숫자보다 크면 앞의 작은 숫자들을 제거
  • 단, K개까지만 제거 가능
  • 이 과정을 Deque로 구현하여 스택처럼 숫자를 쌓고 관리함

---

전체 코드

import java.util.*;

public class Main {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		String num = sc.next();
		
		Deque<Integer> stack = new ArrayDeque<>();
		int removed = 0;
		
		for (int i = 0; i < n; i++) {
			int x = num.charAt(i) - '0';
			
			while (!stack.isEmpty() && removed < k && stack.peekLast() < x) {
				stack.pollLast();
				removed++;
			}
			
			stack.addLast(x);
		}
		
		while (removed < k) {
			stack.pollLast();
			removed++;
		}
		
		for (int digit : stack) {
			System.out.print(digit);
		}
		
		sc.close();
	}
}

---

코드 설명

Deque<Integer> stack

• 숫자를 차례대로 쌓는 스택처럼 사용하는 덱
• 삽입은 addLast(), 제거는 pollLast()로 뒤쪽 기준으로 관리

그리디 핵심 로직

while (!stack.isEmpty() && removed < k && stack.peekLast() < x) {
    stack.pollLast();
    removed++;
}

• 현재 숫자 x가 더 크면 앞의 작은 숫자를 제거하면서 큰 수를 앞에 위치시킴

제거가 부족한 경우

while (removed < k) {
    stack.pollLast();
    removed++;
}

• 아직 제거할 숫자가 남아 있다면 뒤에서부터 더 제거

---

시간 복잡도

• 전체 숫자 N개를 한 번씩만 처리 → O(N)
• Deque의 삽입/삭제는 amortized O(1)

---

Deque로 스택 구현

삽입	삭제	조회	Deque로 스택 구현 시
addFirst()	pollFirst()	peekFirst()	→ Deque 앞쪽(head) 기준으로 사용

나는 뒤쪽 기준으로 사용했는데 보통 앞쪽 기준으로 많이 사용한다고 한다.