[프로그래머스/Python] 탐욕법(그리디) - 큰 수 만들기

풀이

def solution(number, k):
    answer = [] # Stack: 리스트 활용 가능
    for num in number:
    	# 스택이 비어있지않다면
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

• 앞자리에 큰 숫자가 오는 것이 전체 수를 크게 만들 수 있음
• 스택의 마지막 값이 push할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해서 pop을 하는 것
• 시간 복잡도는 $O(n)$
• for num in number => 하나씩 순회
  • 스택이 비어있지않다면 stack.append(num)
  • k가 0보다 크다면
    • 스택의 마지막 값이 num보다 작거나 같다면 계속 반복문
    • 스택의 마지막 값을 pop하고, k-1
    • 스택이 비어있지않거나 k가 0보다 작거나 같다면 break
  • 스택에 num을 append
• k가 0보다 크다면 스택에서 k개만큼 삭제 = 즉, 제거 횟수를 다 사용하지 않았을때 남은 횟수만큼 리스트 뒷부분을 잘라 주는 것