Programmers / 2단계 / 큰 수 만들기 / python / 탐욕법(Greedy)

 

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

 

 

나의 풀이

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

 

 제거하는 수를 제외한 나머지 수의 위치를 변경하지 않고 만들 수 있는 최댓값을 구하는 문제였다.

Stack을 사용해 number 값들을 넣고 while문으로 Stack의 맨 위의 원소보다 number 값이 크면 Stack 원소를 pop함과 동시에 k값을 1 줄여가며 k가 0일 때까지 반복한다.

이렇게 하면 Stack에 남은 원소들로 원하는 답을 구할 수 있지만 332211과 같이 예외가 있을 때 처리할 수 없기 때문에 stack[:len(stack) - k]로 처리하여 예외까지 고려할 수 있다.