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

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

프로그래머스

---

•  풀이
  • 조합으로 풀었더니 시간 초과
  • 최적의 해를 찾는 탐욕법
    • 가장 큰 수를 찾는 것이므로 n자리 숫자를 최대한 크게 만들어주기
    • 이전 숫자가 작으면 제거
    • 숫자가 내림차순이어서 stack에 다 들어가는 경우!!!
      • 이 부분때문에 테스트케이스 12번이 계속 틀렸음
        • '654321'일 때 k가 1인 경우
      • 즉, k개 제거를 못한 경우
      • stack에서 뒤에서 k개를 제거하면 된다
        • stack[:-k]

def solution(number, k):
    stack = []
    for num in number:
        while stack and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
	# 제거를 다 못했다면
    if k > 0:
        stack = stack[:-k]
    return ''.join(stack)