백준 2812 크게 만들기 Python

🐸 문제 정보

2812번: 크게 만들기

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

12.49m + a

 

📝 풀이

골3치고 너무 쉬워서 후딱 풀었는데... 뭔갈 놓친건지 계속 틀리다가 겨우 고쳐서 맞았다ㅠㅠ

풀이자체는 아이디어가 떠오르는대로,

숫자를 하나씩 스택에 넣지만, 앞에 해당 수보다 작은 수가 있다면 k번까지 pop 해주는 식으로 풀었다.

핵심은 이 pop 횟수에 따라 결과 출력이 달라진다는 점이었다.

때문에 k값 자체에 변동을 줘서, k가 0일 경우와 아닐경우를 분리해서 출력했더니 맞았다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
num = list(map(int, list(input().rstrip())))
stack = []

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

if k == 0:
    print(''.join(map(str, stack)))
else:
    print(''.join(map(str, stack[:-k])))