골드5 : 스택 문제이다.
풀이
비슷한 문제를 한 3번 봤다. 근데 그 때는 heap을 사용해서 뒤에서 가장 큰 문자를 계속해서 뽑는 것으로 문제를 해결했다.
그런 방식으로 해당 문제를 다시 풀려했으나, 밑에 알고리즘 분류를 봤는데 stack…이더라.
그래서 같은 문제를 다른 방향으로 풀 수 있다는 것도 좀 배우고, 좀 약한 stack도 보충할 겸 참고해서 풀었다. stack은 아무래도 약간 증가하는 수열같은 것을 만들 때 n의 시간 복잡도를 가지고 만드는데 굉장히 유용한 것 같다.
Code
n, k = map(int, input().split())
target = input()
stack = []
_k = k
for char in target:
while stack and _k > 0 and stack[-1] < char:
stack.pop()
_k -= 1
stack.append(char)
print("".join(stack)[: n - k])
n, k = map(int, input().split())
number = input()
removed = 0
stack = []
for now in number:
while stack and stack[-1] < now and removed < k:
stack.pop()
removed += 1
stack.append(now)
print("".join(stack[:n - k]))
저번이랑 똑같이 풀었는데 똑같은 부분 (n-k)에서 또틀림..