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

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

문제유형 : 그리디 알고리즘, 파이썬

해결방법

스택에 number의 첫번째 인자를 넣어두고 다음 숫자랑 비교해 나가면 된다.

조건으로 스택이 비어있지는 않은지, 들어올 숫자가 제거할 숫자보다 큰지, k가 존재하는지를 반복해서 확인한다. 조건에 맞다면 스택에서 pop() 연산을 하고 k를 1 제거해 준다.

스택에는 다음 숫자는 여과없이 일단 계속 넣어준다.

마지막으로 k가 0이 아니라면 뒷자리부터 그냥 상관없이 k개만큼 빼주면 된다.

👉 이미 앞자리대로 큰 수대로 정렬되 있는 상태이므로 가능하다.

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)