프로그래머스 / 큰 수 만들기 / python

def solution(number, k):
    answer = ""
    stack = []
    number = map(int, list(number))
    
    for n in number:
        while stack and k and stack[-1] < n:
            stack.pop()
            k -= 1
        stack.append(n)
    while k:
        stack.pop()
        k -= 1
    
    for i in stack:
        answer += str(i)
    
    return answer

처음에넌 itertools의 combination을 사용해서 시도했다.
당연하게도 히든케이스에 대해서 시간 초과가 많이 발생했다

그 다음은 도저히 떠오르는 방법이 없어서 인터넷으로 검색해서 stack에대한 힌트를 얻고 바로 위와 같이 작성했다.

stack이 채워진 상태이고 k가 0이 아니고 stack의 마지막 숫자가 현재 n보다 작다면 -> stack의 마지막 숫자를 지우면 더 큰 수가 된다는 뜻이다.

이런식으로 진행하며 마지막에 k가 남아있다면 뒤에서 부터 k만큼 pop 해줌으로써 정답을 구할 수있다.