[스택 / python] 백준 2812. 크게 만들기

풀이

첫 번째 시도

n, k = map(int, input().split())
li = [i for i in input()]

find_length = n - k
tmp = li[:k]
idx = tmp.index(max(tmp))
k -= idx
li = li[idx:]
targets = list()
for i in range(len(li)-1):
    if not k: break
    if li[i] < li[i+1] : li.pop(i); k -= 1 # O(N^2) 발생 지점
print(''.join(map(str, li)))

위 풀이는 단순하게 문제를 바라본 경우 나올 수 있는 로직이고, 이는 시간복잡도를 고려하지 않은 풀이이다. 리스트의 pop() 연산을 수행하기 위해선 O(N)이 될 수 있음을 항상 유념해야 한다.

두 번째 시도

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
li = [i for i in input()]

stack = []
ans = []
for i in range(len(li)):
    while k and stack and li[stack[-1]] < li[i]:
        stack.pop()
        k -= 1
    stack.append(i)

for i in stack:
    ans.append(li[i])
print(''.join(ans))

위 풀이는 지난 오큰수 때의 풀이를 활용한 것이다. 기준이 되는 수를 기점으로 당장 큰 수를 골라내는 것이 동일하므로 스택을 활용하여 적용할 수 있다. 위의 경우 stack의 pop()을 활용하지만, 그 stack의 크기가 쉽게 커지지 않으므로 시간복잡도에선 무리가 없다. 하지만 위 로직의 경우 k가 0이 되었을 때 남은 인덱스가 전부 stack에 쌓이므로 목표하는 자릿수의 답을 도출해내기엔 부족했다.

세 번째 시도

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
length = n - k
li = [i for i in input().strip()]

stack = []
ans = []
for i in range(len(li)):
    while k and stack and li[stack[-1]] < li[i]:
        # ans.append(li[i])
        stack.pop()
        k -= 1
    stack.append(i)

for i in stack:
    ans.append(li[i])

# 수정
while len(ans) > length:
    ans.pop()

print(''.join(ans))

위와 같이 길이가 넘치게 되는 것을 대비하여 while/pop을 적용하면 정답을 얻을 수 있다.