[프로그래머스] 큰 수 만들기 - Python (Greedy)

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

프로그래머스

greedy 라길래 처음엔 단순하게 작은 숫자들 차례대로 구해서 전체 숫자에서 지워주는 방식으로 갔다 

그런데 이 방식은 test case 3에서 걸린다.. 

"4177252841" 의 경우 가장 작은 숫자들 k 개 고르면 1, 1, 2, 2 인데 이걸 linear 하게 지우면 얻는 값이 477584 가 나오게 된다. 

but 실제로는 775841이 만들 수 있는 가장 큰 수라는 반례가 생긴다. (Greedy는 반례가 없는지 고려해봐야 한다는게 어렵당~~ ) 

이런 반례가 생기는 이유는, 선형적으로 탐색했기 때문에 생기는 것이고 이를 해결하기 위해서는 전체 숫자에서 지금 만드는 값이 최댓값인지 확인해주어야 한다.

이를 위해 stack 구조를 활용해야 한다!!

주요 로직은 제거할 숫자가 아직 k개 남았다면, stack 에서 가장 위에 있는 숫자가 현재 number에서 확인하고 있는 숫자보다 크거나 같을 때까지 pop() 하면서 k의 개수를 1개씩 줄여주는 것이다. 

1 9 2 4 가 있다면 

stack = [1] , k = 2

stack = [9] , k = 1 (제거한 숫자 : 1)

stack = [9, 2] , k = 1 (제거한 숫자 : 1)
9 > 2 이므로 2는 그대로 push 한다. 

stack = [9, 4] , k = 0 (제거한 숫자: 1, 2)
2 < 4 이고 아직 k > 0 이므로 2는 pop 한다. 9 > 4 이므로 비교 종류하고 4를 스택에 push한다. 

1, 9, 2, 4, 처리를 모두 해주었으므로 현재 stack에 남아있는 숫자를 문자열로 만들어 버리면 94가 된다. 

def solution(number, k):
    answer = ''
    arr = [int(i) for i in number]
    stack = []
    n = len(number)
    for i in range(n):
        if not stack:
            stack.append(number[i])
            continue 

        # 현재 숫자보다 stack 맨 위의 숫자가 같거나 클때까지 pop
        while k > 0 and stack and stack[-1] < number[i]:
            stack.pop() # 숫자 제거 
            k -= 1 

        stack.append(number[i])
                
    answer = ''.join(stack)
    return answer