[Greedy] 백준 2812번 “크게 만들기” Python 풀이

문제 링크

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

풀이

• 큰 수가 되려면 높은 자리수의 숫자가 커야합니다.
• 그래서 스택을 이용합니다.
• 예를 들어, 4177252841 이고 k = 4이면 775841이 최대값이겠죠?
• 먼저 4를 stack에 집어넣습니다.
  • stack = [4]
• 다음 1을 stack에 넣어야 하는데, stack의 최근 값인 4보다 1이 작거나 같죠? 그래서 그냥 stack에 1을 넣습니다.
  • stack = [4, 1]
• 다음 7을 stack에 넣어야 하는데, stack의 최근 값인 1보다 7이 크죠? 그래서 1을 pop 합니다.
  • stack = [4], k = 3
• 아직 stack의 최근 값인 4보다 7이 크죠? 그래서 4를 pop 합니다.
  • stack = [], k = 2
• 이제 stack에 7을 집어넣습니다.
  • stack = [7]
• 다음 7을 stack에 넣어야 하는데, stack의 최근 값인 7보다 7이 작거나 같죠? 그래서 그냥 stack에 7을 넣습니다.
  • stack = [7, 7]
• 다음 2를 stack에 넣어야 하는데, stack의 최근 값인 7보다 2가 작거나 같죠? 그래서 그냥 stack에 2를 넣습니다.
  • stack = [7, 7, 2]
• 다음 5를 stack에 넣어야 하는데, stack의 최근 값인 2보다 5가 크죠? 그래서 2를 pop하고 5를 넣습니다.
  • stack = [7, 7, 5], k = 1
• 다음 2를 stack에 넣어야 하는데, stack의 최근 값인 5보다 2가 작거나 같죠? 그래서 그냥 2를 넣습니다.
  • stack = [7, 7, 5, 2]
• 다음 8을 stack에 넣어야 하는데, stack의 최근 값인 2보다 8이 크죠? 그래서 2를 pop 합니다.
  • stack = [7, 7, 5], k = 0
• 이제 k=0 이므로 나머지 숫자들은 그냥 추가합니다.
  • stack = [7, 7, 5, 8, 4, 1]

코드

import sys

N, K = map(int, sys.stdin.readline().split())
num = list(sys.stdin.readline())
k = K # 기존 K 값 저장
stack = []

for i in range(len(num)):
    # 뺄 수 있는 횟수가 남아있고, 스택의 값이 남아있고, 현재 값이 stack의 최근값보다 클 경우 POP
    while (k > 0 and stack and num[i] > stack[-1]):
        stack.pop()
        k -= 1
    # 그 외 경우엔 현재 값을 stack에 삽입
    stack.append(num[i])

# 예외 케이스) 5 2 / 19876 일 경우, 답은 987
print("".join(stack[:N-K]))