읽는데 8분정도 소요되는 글입니다. 감사합니다.
목차
1. 문제 설명
2. Monotonic Stack이란?
3. 문제 풀이
1. 문제 설명
402. Remove K Digits
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
음수가 아닌 num(string)과 k(int)가 주어졌을 때 num에서 k자리 만큼 제거한 후 가질 수 있는 가장 작은 값을 반환하는 문제입니다.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Constraints:
1 <= k <= num.length <= 10^5
num consists of only digits.
num does not have any leading zeros except for the zero itself.
여러가지로 접근해보았는데 생각보다 어려워서 고민 후에 Related Topic을 확인했습니다. 확인해보니 Monotonic Stack 이라는 방법이 나왔는데 저는 해당 방법을 잘 알지 못해서 공부 후 문제 해결을 목적으로 해당 블로그 글을 쓰게 되었습니다.
2. Monotonic Stack이란?
정의는 데이터를 일정한 순서(증가 또는 감소)로 유지하면서 스택에 저장하는 데이터 구조라고 합니다.
단순히 표현하면
stack = [1, 2, 3, 4, 4, 5]
stack = [5, 4, 3, 3, 1, 0]
위와 같은 스택 구조가 Monotonic stack입니다.
해당 말만 듣고는 문제 풀이에 어떻게 적용할 지 감을 잡기 힘들어서 예제 하나를 준비했습니다.
예제 문제: 배열이 주어졌을 때, 각 원소의 다음에 위치하면서 해당 원소보다 큰 첫번째 원소를 구해라.
단, 자기자신이 가장 큰 수일 경우 -1을 반환한다.
Example
nums: [1, 5, 4, 9, 3, 2]
c++ 풀이 방법:
#include <iostream>
#include <vector>
#include <stack>
std::vector<int> nextGreaterElement(const std::vector<int>& nums) {
std::stack<int> s;
std::vector<int> result(nums.size(), -1);
for (int i = 0; i < nums.size(); ++i) {
while (!s.empty() && nums[i] > nums[s.top()]) {
int index = s.top();
s.pop();
result[index] = nums[i];
}
s.push(i);
}
return result;
}- (i == 0) s stack이 비어있기 때문에 s에 0이 담깁니다.
s의 상태 = [0] - (i == 1) s가 비어있지 않고 nums[1](value: 5) > nums[s.top()](value: 1) 의 조건을 만족하기 때문에 result[0]에는 5가 담깁니다.
- (i == 1) s에는 1이 담깁니다.
s의 상태 = [1] - (i == 2) while문의 조건을 충족하지 않기 때문에(num[2] > nums[1]) 반복문을 넘어갑니다.
s의 상태 = [1, 2] - (i == 3) while문의 조건을 충족하기 때문에 result[2] = 9, result[1] = 9 가 담깁니다. 반복문을 종료하고 넘어갑니다.
s의 상태 = [3] - (i == 4) while문의 조건을 충족하지 않기 때문에 반복문을 종료하고 넘어갑니다.(num[4] > num[3])
s의 상태 = [3, 4] - (i == 5) while문의 조건을 충족하지 않기 때문에 반복문을 종료하고 넘어갑니다.
s의 상태 = [3, 4, 5]
result: [5, 9, 9, -1, -1, -1]
s: [3, 4, 5]
이 때, stack(s)에 남아있는 요소들은 다음 큰 수를 찾지 못한 요소들입니다.
3. 문제 풀이
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
st = list()
for n in num:
# 현재 숫자가 스택의 최상단 숫자보다 작으면 최상단 숫자를 제거
while st and k and st[-1] > n:
st.pop()
k -= 1
if st or n is not '0':
st.append(n)
if k:
st = st[0:-k]
return ''.join(st) or '0'
문제를 c++로 풀려고 했었는데 아직 문법도 익숙치 않아 힘들어 python으로 먼저 작성했습니다.
요지는, string type의 num을 최상단부터 스택에 넣고 마주치는 숫자가 스택의 최상단 숫자보다 작으면 스택을 pop해주는 것이었습니다.
코드가 많지 않아 이해가 어렵지 않으시겠지만 추가적으로 예제를 설명드린다면
Example 1
num = "54321"
k = 2
라고 가정하고 해당 로직을 적용해보겠습니다.
stack=[5]
stack=[4] / 5 > 4 의 조건을 만족하기 때문에 stack을 pop하고 4가 append됩니다.
stack=[3] / 4 > 3 의 조건을 만족하기 때문에 stack을 pop하고 3이 append됩니다.
stack=[3, 2]
stack=[3, 2, 1]
Example 2
이번에는 거꾸로 num = "12345"
k = 2
라고 가정하고 해당 로직을 적용해보겠습니다.
stack=[1]
stack=[1, 2]
stack=[1, 2, 3]
stack=[1, 2, 3, 4]
stack=[1, 2, 3, 4, 5]
반복문을 탈출한 뒤,
if k: / 조건에 막혀 아래의 결과가 도출됩니다.
stack=[1, 2, 3]
결과
개인 소감...
솔직히, 위와 같은 예제에 대해서 공부해도 바로 이해하고 적용하기 어려웠던 문제였습니다. 그래도 특정상황에서 O(n^2)를 O(n)의 시간복잡도로 만들어주는 것은 굉장히 즐거운 일이기에, 그 특정 상황이 충족된다면, 써볼 수 있도록 노력하면 좋을 것 같습니다. 긴 글 읽어주셔서 감사합니다.
