https://programmers.co.kr/learn/courses/30/lessons/42883
def solution(number, k):
stack = []
for num in number:
while (stack and stack[-1] < num and k > 0):
k -= 1
stack.pop()
stack.append(num)
if (k != 0):
stack = stack[:-k]
return ''.join(stack)
처음엔 Combinations
으로 풀면 한줄로도 풀수있겠다고 생각해서 제출했지만 당연히 시간초과가 떴고 그뒤로 Counter
를 이용해서 풀수 있지 않을까 생각했지만 어림도 없었다. 문제 유형부터 그리디라 생각해서 그리디로 어떻게 풀지.. 하면서 테스트케이스를 머리속으로 푸는 방식을 구현했어야했는데 제대로 나오지않아 검색해보니 스택으로 푸는방법이 있었다. 왜 이걸 생각못했을까 아쉬웠다.
number
를 for문 돌리면서 stack
에 가장 윗부분과 현재 num
을 비교해주면서 k
가 충분하면 pop
을 해주고 num
을 stack
에 넣는다. 만약 k
가 아직 0
이상이라면 현재 스택에서 끝부분을 남은 k
만큼 잘라 리턴한다.