[그리디] 큰 수 만들기 (feat. stack, list[:-m])

def solution(n,m):
    answer = ''
    
    stack = []
    for v in n:
        while stack and m > 0 and v > stack[-1]:
            stack.pop()
            m -= 1
        stack.append(v)
    if m != 0:             # m개 제거 못하고 for문이 끝남. 큰 수 -> 작은 수 정렬되어있는 상태
        print(stack)
        print(m)
        stack = stack[:-m] # 큰수->작은수 정렬된 상태므로 맨 뒤에서 m개 제거
        print(stack)
    answer = ''.join(map(str, stack))
    # print(answer)
    return answer

    # answer = ''.join(lst)


solution('654321', 1)

 

두번 풀었던 건데, 다시 푸니까 못푼 문제.

1. 입력된 문자열 '298375'에서 하나씩 꺼내는 게 - 첫 번째 for 반복문

2. stack(선택한 문자들 순서대로 쌓는 리스트)을 돌면서 마지막에 넣은 값(stack[-1])이 새로 넣을 값(v)과 비교해서 작으면 pop

    만약

      stack = [1,2]

      v = 3

    일 경우, while stack을 돌며 pop 으로 2 꺼낸 다음에 1 꺼내게 됨.

3. m 은 꺼낼 문자의 개수를 나타내는 숫자, 문자를 하나씩 꺼낼 때마다 -1 됨.

만약 '54321'에서 1개를 제거해야 한다고 가정해보자. stack에 5432까지 들어간 상황에서, 마지막 1을 비교할 때, stack마지막 요소 2가 1보다 크니까 안꺼내고 stack = 54321이 된 채로 for문이 끝나게 되면 m은 여전히 1로 남는다. 1개를 제거하지 못한 채로 for문이 끝나면 뒤에서부터 m개를 제거해야 한다. 따라서 if m !=0 : stack[:-m] 구문이 추가된다.

 

이중 반복문인데, while에 m조건, stack 조건, 새값과의 비교조건이 한번에 들어가 있다. 여기가 핵심이다. whlie의 조건때문에 m의 역할이 명확해졌다..! 천재..