프로그래머스 Level 2 | 큰 수 만들기 | Python

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

문제 파악

문자열 형식으로 숫자가 주어진 number와 제거할 숫자의 개수 k를 입력받았을 때, number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 하는 문제이다.

예시 1

number로 "1924", k로 2를 입력받았다면 1과 2를 제거한 "94"가 최댓값으로 답이 된다.

어떻게 풀 수 있을까?

왼쪽 자릿수부터 가능한 한 크게 고르면 전체가 최대가 된다. (탐욕법 = 지금 당장 이득인 쪽으로 진행하기)

number를 왼쪽부터 하나씩 보며,
새로운 숫자를 스택에 push한다.

다만, 새 숫자(num)가 기존의 마지막 숫자보다 크다면
— 작은 수는 뒤로 갈수록 손해니까 —
스택의 마지막 숫자를 pop()으로 제거한다.
(k는 버릴 수 있는 횟수를 의미하므로, 제거할 때마다 1 감소)

위 과정을 조건이 맞는 동안 반복해야 하므로 while문을 쓴다.

해답 및 풀이

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

    for num in number:
        # 스택이 비어있지 않고, 마지막 숫자가 지금 숫자보다 작고, 아직 버릴 수 있다면
        while stack and stack[-1] < num and k > 0:
            stack.pop()   # 더 작은 건 제거
            k -= 1        # 버린 개수 1 감소
        stack.append(num) # 현재 숫자 push
    
    # 다 돌았는데도 k가 남으면, 뒤에서 k개 제거 
    if k > 0:
        stack = stack[:-k]

    return ''.join(stack)

for문으로 전체 흐름을, while문으로 stack을 돌며 새로 자리를 정해주는 로직이 중요했다.