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

코드

시간초과 코드

from itertools import combinations

def solution(number, k):
    answer = ''
    arr = list(combinations(number, len(number)-k))
    for i in max(arr):
        answer += i
    return answer

combination 자체가 무리인 듯 하다

 

정답 풀이 1

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

 

정답 풀이 2

from collections import deque
def solution(number, k):
    q = deque()
    stack = deque()

    for n in number:
        q.append(n)

    while q and k:
        while stack and stack[-1] < q[0]:
            stack.pop()
            k -= 1
            if not k:
                break
        stack.append(q.popleft())

    while k and stack:
        stack.pop()
        k -= 1

    return "".join(stack + q)