[Programmers] Lv2. 큰 수 만들기 Python 문제 풀이

문제

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

프로그래머스

 

어떻게 풀었는가

전형적인 스택 기반 그리디 문제다.

핵심 아이디어

가장 큰 수를 만들려면, 앞자리에 가능한 한 큰 숫자가 와야 한다. 이를 위해 스택을 사용한다. 새로운 숫자를 넣기 전에 스택의 top이 현재 숫자보다 작다면 pop해서 제거하는 방식이다.

구현 흐름

1. 숫자를 앞에서부터 하나씩 순회한다.
2. 스택의 top이 현재 숫자보다 작고, 아직 제거 횟수(k)가 남아있다면 pop한다. 이 과정을 조건이 만족하는 동안 반복한다.
3. 현재 숫자를 스택에 push한다.
4. 순회가 끝난 뒤에도 k가 남아있다면(예: "99999"처럼 내림차순인 경우), 뒤에서 k개를 잘라낸다.

예를 들어 "4177252841"에서 4개를 제거하는 과정을 보면, 4를 넣고 → 1은 4보다 작으니 그냥 넣고 → 7이 올 때 1, 4를 차례로 pop하는 식으로 진행된다. 결국 앞자리부터 최대한 큰 숫자가 남게 된다.

시간복잡도

각 숫자는 스택에 최대 한 번 push되고 한 번 pop되므로 O(N)이다. 문자열 길이가 최대 1,000,000이지만 충분히 처리 가능하다.

 

코드

def solution(number, k):
    stack = []
    for digit in number:
        while k > 0 and stack and stack[-1] < digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    if k > 0:
        stack = stack[:-k]

    return ''.join(stack)