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

큰 수 만들기

문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

k개의 수를 제거했을 때 가장 큰 수를 얻기 위해서는 가능한 앞에서 작은 수를 빼야함을 직관적으로 알 수 있다.
숫자를 앞에서부터 탐색하면서 주어진 숫자를 하나씩 꺼내어 모은다.
앞에 등장한 것보다 작은 것들을 제거한다.

1. 꺼낸 숫자를 모을 스택 초기화
2. 스택의 원소가 존재하고 제거한 숫자가 k개 이하면서 앞에 등장한 것보다 작은 경우 pop하여 제거한다.
3. 반복문 이후 제거한 숫자가 k개 이하면 그 만큼 뒤에서 제거한다.

def solution(number, k):
    stack = []
    for i, num in enumerate(number):
        while stack and stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
        if k == 0:
            stack += list(number[i:])
            break
        stack.append(num)
    if k > 0:
        stack = stack[:-k]
    answer = ''.join(stack)
    return answer