[Python] BOJ / 2812번 / 크게 만들기

2812번: 크게 만들기

---

📝 풀이

• N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램
• 전체 자릿수에 대해서 아래 과정을 반복한다
  • 스택에 i번째 자릿수 값을 저장
  • 숫자 제거 횟수가 남아 있고(del_cnt > 0) 스택에 저장되어 있는 원소가 있는 경우
    • 스택의 끝 수와 i번째 수를 비교하여 i번째 수보다 작은 스택의 끝 수를 제거하고 숫자 제거 횟수를 갱신시킴
• 결과를 출력할 때에는 스택에 담겨있는 수를 전체 자릿수에서 제거할 횟수를 뺀 만큼 순서대로 출력

---

💻 소스코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
nums = list(map(int, input().strip()))

# 숫자 제거 횟수, 결과 리스트
del_cnt, stack = k, []

# n자리까지 반복
for i in range(n):
    while del_cnt > 0 and stack:
        # i번째 수보다 작은 리스트의 끝 수를 모두 제거
        if stack[len(stack) - 1] < nums[i]:
            stack.pop()
            del_cnt -= 1
        else:
            break
    stack.append(nums[i])

# 결과 리스트에 담겨있는 수를 전체 자릿수에서 제거할 횟수를 뺀 만큼 출력
for i in range(n - k):
    print(stack[i], end = '')