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

https://school.programmers.co.kr/learn/courses/30/lessons/42883#

프로그래머스

풀이

풀이 1 : 앞에서부터 순회하면서, 뒤의수보다 작으면 빼기

위와 같은 방식으로 number를 업데이트 해나가는 방법

def solution(number, k):
    number = list(number)
    # 앞에서부터 순회하면서, 뒤의수보다 작으면 빼기
	n = len(number)
    while k:
        for i in range(n-1):
            if number[i]<number[i+1]:
                del number[i]
                k-=1
                n-=1
                break
            # 끝까지 갔을때
            elif i==n-2:
                del number[n-1]
                k-=1
                n-=1
    if k:
        number = number[:-k]

    return ''.join(number)

정답은 도출 가능하지만, 시간 초과 발생

• del 함수 : O(n)
• number를 업데이트하고난 후, 다시 한번 순회하기 때문에 더 많은 시간 소요

풀이 2 : Stack 활용

def solution(number, k):
    from collections import deque
    # stack의 마지막값이 push할 값보다 작은 경우에 Pop
    stack = []
    number = deque(list(number))
    while number:
        num = number.popleft()
        while stack and stack[-1]<num and k:
            stack.pop()
            k-=1
        stack.append(num)
    number = stack
    if k:
        number = number[:-k]
    return ''.join(number)