큰 수 만들기

프로그래머스

from itertools import combinations

def solution(number, k):
    n = len(number)
    l = list(map(''.join, combinations(number, n-k)))
    l = list(map(int, l))

    return str(max(l))

이렇게 푸니 테스트케이스에서 두개 빼고 시간초과가 떴다..
그리고 심지어 int형으로 변환 안해도 됨..
int형으로 안바꾸면 테스트케이스에서 네개 통과하고 나머지 시간초과뜬다ㅋ..
결국 방법 자체가 이렇게 하는 게 아니란 소리인데 찾아보니 스택을 쓰는거였다.

진짜 신기하다..

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

k개의 수를 뺄 수 있으므로 숫자를 비교해가며 큰 수를 찾을때까지 스택의 top원소를 빼고, k를 감소시켜준다.
조건에 해당되지 않으면 원소를 스택에 넣는다.

''.join(리스트)는 리스트의 원소를 하나로 합쳐주고,
그냥 stack이 아니라 stack[:len(stack)-k]를 하는 이유는 "999"가 주어졌을 때 k가 2인 경우 9가 나와야하는데 숫자가 모두 같은 관계로 stack에는 999가 모두 넣어지게 되어 999가 출력된다. 따라서 이 때에는 k를 뺀 개수만큼만 합쳐서 리턴하면 된다.