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

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

프로그래머스

 

📄문제

📝 코드

스택 사용 

def solution(number,k):
    stack = []

    for num in number:
        while k > 0 and stack and stack[-1] < num:
            stack.pop()
            k -= 1
            
        stack.append(num)
    
    if k > 0: # k가 0보다 크다면
        stack = stack[:-k]

    return ''.join(stack)

• 스택 사용
• number에서 k개의 숫자를 제거하여 큰 숫자를 만드는 것이 목표이므로, 스택에 있는 숫자와 현재 숫자를 비교하여
  스택의 숫자가 작다면 스택에서 제거한다.
• k가 0보다 큰 경우 슬라이싱을 이용하여 stack 에서 -k번째 요소까지 추출한다.

ex) number = '123432', k = 4

1. stack = [ 1 ], k = 4
2. stack = [ 2 ], k = 3
3. stack = [ 3 ], k = 2
4. stack = [ 4 ], k = 1
5. stack = [ 4, 3 ] , k = 1
6. stack = [ 4, 3 , 2 ] , k = 1
7. k가 0보다 크므로,
   stack = stack[ : -k ]
   stack = [ 4, 3 ]

📝 이전 코드

조합 사용 

def solution(number, k):
    answer = []
    for num in combinations(number,len(number)-k):
        answer.append(''.join(list(num)))
    return max(answer)

 

• combinations 함수 사용 시 모든 조합을 생성하므로 시간복잡도가 크게 증가해 시간 초과 에러가 발생한다.