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

문제 파악

문자열로 된 숫자 number에서 정확히 k개의 숫자를 제거해 만들 수 있는 가장 큰 수를 반환하는 문제

예시 1에서 number = "1924", k = 2→ "94"
순서는 유지해야 하고, 숫자 제거는 임의의 위치에서 가능하다.

왼쪽부터 보면서, 더 큰 수를 만들 수 있으면 앞에 있는 작은 수를 지우는 로직으로 가면 풀 수 있다.

1. 숫자를 왼쪽→오른쪽으로 한 자리씩 보면서 스택에 쌓는다.
2. 현재 숫자가 스택 맨 위보다 크고, 아직 지울 수 있는 횟수 k가 남았다면
   스택에서 pop(작은 수 제거) 한다. (더 큰 앞자리를 만들기 위함)
3. 위 조건이 깨질 때까지 반복 후, 현재 숫자를 push.
4. 끝까지 했는데도 k가 남았다면 → 뒤에서 추가로 k개 제거 (이미 비내림차순이라 뒤를 잘라내는 게 최선)
5. 스택의 숫자를 이어 붙이면 정답.

이 방식이면 매 자릿수는 최대 한 번 push, 한 번 pop → 전체 O(n).

정답 및 풀이

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

    for ch in number:
        # 현재 자리 ch가 더 크면, 앞의 작은 수들을 지워서 자릿값을 키운다
        while stack and to_remove > 0 and stack[-1] < ch:
            stack.pop()
            to_remove -= 1
        stack.append(ch)

    # 아직 못 지운 게 남았다면 뒤에서 자르기
    if to_remove > 0:
        stack = stack[:-to_remove]

    return "".join(stack)