[백준] 2812 파이썬(python) : 크게 만들기 - (★)

2812번: 크게 만들기

 

 

 

#1이 단조스택을 이용하는것 같지만 cnt가 양수일때만 적용되므로 마지막 stack이 단조롭지 않을 수 있다.

 

import sys
n, k = map(int, sys.stdin.readline().split())
string = list(sys.stdin.readline().rstrip())
stack, cnt = [], k
for char in string:
    while stack and stack[-1] < int(char) and cnt: #1
        stack.pop()
        cnt -= 1
    stack.append(int(char))
for idx in range(n-k):
    print(stack[idx], end='') #2

 

# 1 : (1)answer 스택이 비어있지 않고 (2)삭제가능한 횟수(cnt)가 남아 있고 (3)answer의 마지막 값이 num보다 작은 경우 

(1) : answer이 처음엔 비어있기 때문에 첫 문자는 while문을 건너뛰고 answer.append(num)이 된다. 

맨 처음이 아니면 스택이 비어있을리 없기 때문에 (1)의 역할은 여기서 끝난다.

(2) , (3) : 두 조건이 같아야지 answer의 마지막 값을 지울 수 있다. 그리고 지운뒤 while문이 끝나면 num을 스택에 추가한다.

 

# 2 n에서 k개 만큼 숫자를 빼니까 0 ~ n-k 만큼 출력

 

그림의 예시에서처럼 마지막에 스택에 4 4 4 이렇게 3개의 원소가 남게 되는데 원하는건 5개에서 3개를 뺀것을 원하니까 2개인 4 4 만 출력해 줘야한다.

 

---

6198번: 옥상 정원 꾸미기