remove-k-digits
학습 키워드: 문자열, 스택, 그리디
문제 링크: https://leetcode.com/problems/remove-k-digits/?source=submission-noac
문제 설명
주어진 문자열 num은 비음수가 나타내는 정수를 나타내며, 정수 k가 주어진다. num에서 k개의 숫자를 제거한 후 가능한 가장 작은 정수를 반환하시오.
제한 조건
- 1 <= k <= num.length <= 105
- num consists of only digits.
- num does not have any leading zeros except for the zero itself.
-> "0200"과 같은 케이스는 "200"으로 치환된다.
문제 풀이
이 문제에서 가장 핵심적인 알고리즘은 monotonic stack(단조 스택)이다. 단조스택이란 배열의 원소가 increase/decrease('기울기' = 0 포함) 순으로 정렬되어 있는 스택을 말한다. 해당 알고리즘을 알기 쉽게 설명한 영상을 같이 첨부한다.
(https://youtu.be/Dq_ObZwTY_Q?si=YnhQn_2WEkAOZS7B)
어떤 숫자의 자릿수를 제거 해서 가장 작은 숫자를 만들 때 가장 작은 숫자를 만들기 위해서는 가장 앞자리 숫자가 작아야 한다. 앞에서부터 탐색하며 원 문자열에서 숫자를 제거하는 것이 아닌 increase monotonic stack에서 원소들을 추가 및 제거해주면서 반환할 가장 작은 정수를 만들어야 한다.
또한, for loop를 다 돌았을 때 만약 제거해야 할 숫자(k)가 더 남았다면 뒤에서부터 제거해준다. 증가하는 수열이기 때문에 제거했을 때 가장 최소인 정수를 반환한다면 가장 큰 수를 제거해줘야하기 때문이다.
만약 가장 앞자리 수가 "0"이라면 자릿수를 k의 감소 없이 제거할 수 있으므로 숫자가 급격히 작아지고 단조스택을 이용한다면 "0"을 별도로 처리하지 않아도 되는 점이 큰 장점이다.
여기서 문자열 함수가 활약을 하는데 lstrip 함수를 사용하여 앞의 0이 몇개든 제거할 수 있게 만들었다. 끝처리로 반환 type이 None이라면 "0"을 반환하게 했다.
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
inc_stk = []
for i in range(len(num)):
while inc_stk and inc_stk[-1]>num[i] and k>0:
inc_stk.pop()
k-=1
inc_stk.append(num[i])
while inc_stk and k>0:
inc_stk.pop()
k-=1
answer = "".join(inc_stk).lstrip("0")
return answer if answer else "0"코멘트
알고리즘 문제의 풀이들을 보면 스택을 정말 잘 활용하는 경우가 많은 것 같다. 오히려 힙이나 큐 문제들은 써야할 상황이 보이는 반면에 스택은 바로 꺼내서 쓰기 어려운 것 같다.
