[Python] 백준 2812 - 크게 만들기 문제 풀이

Overview

BOJ 2812번 크게 만들기 문제 Python 풀이
분류: 그리디 (Greedy)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
input = lambda: stdin.readline().rstrip()


if __name__ == "__main__":
    N, K = map(int, input().split())
    num = list(map(int, input()))

    stack = []
    for i in range(N):
        while K > 0 and stack and stack[-1] < num[i]:
            stack.pop()
            K -= 1
        stack.append(num[i])

    while K > 0:
        stack.pop()
        K -= 1

    print(''.join(map(str, stack)))

숫자의 각 자리 숫자들을 앞에서부터 차례로 탐색하며 Stack 자료구조에 저장한다. 그리고 stack에서 현재 자리의 숫자보다 작은 값들을 꺼내어 제거한다.
위 단계들을 최대 K번 반복하고, 제거된 숫자가 K개 보다 적은 경우, 스택 뒤에서 남은 개수만큼 제거한다.