알고리즘 분류

  • 탐욕법
  • 스택

알고리즘 유도

사실 이 문제는 사칙연산이나 괄호매칭 문제와도 유사하다.

각 숫자마다 우선순위가 존재하며, 지금 현재 우선순위에 따라 최적해가 결정되는 탐욕법 문제이다.

정확히 k개를 제거하는게 목적이며, 만약 n < k인 상태에서 스택의 top이 현재 숫자보다 작다면 더 큰 숫자를 만들 수 있다는 것을 의미한다.

그리고 최종적을로 스택에 남은 원소를 그대로 답으로 쓰면 되는데, 만약 여전히 n < k라면 0부터 n-k-1번째 원소까지 출력하면 된다.

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(number, k):
    st = []
    n = 0
    
    for x in number:
        while n < k and st and st[-1] < x:
            st.pop()
            n += 1
        st.append(x)
    
    if n < k:
        st = st[:n-k]
    
    return ''.join(st)