문제 소개
'Remove K Digits' 문제는 4월 11일 Daily LeetCode Challenge 문제로 제시된 문제이다. 양수 num이 주어졌을 때, k만큼의 숫자를 제거하여 만들 수 있는 수 중 가장 작은 수를 계산해야 한다.
문제 풀이
예시들을 보다 보니, num에서 k만큼 수를 제거해서 가장 작은 수를 만들 수 있는 방법은, 수의 앞부분에 상대적으로 작은 부분들을 남겨놓는 것으로부터 실마리를 찾을 수 있었다. 수의 앞부분으로 갈수록 자리수가 커지고, 따라서 수의 크기에 영향을 미치는 비중이 커지기 때문에 앞부분에 있는 수가 작을 수록 구하고자 하는 값에 가깝다.
나의 아이디어는, num의 구성요소 중 가장 작은 값(0, 1, 2, 3 ···)을 찾아내서, 그 수의 앞을 먼저 쳐내면서 count를 세고, count가 k만큼 충분하지 않다면 그 수의 뒷부분을 또다시 쳐내는 것이었다. 그런데 만약len(num[:minValueIndex])가 k보다 크다면? 그 중에서 다시 선별 작업(작은 수를 앞부분에 남기기)에 들어가야 한다. 그리고 만약 len(num[minValueIndex+1:])가 k보다 크다면? 그 중에서 다시 선별 작업에 들어가야 한다. 이는 재귀적으로 정의될 수 있는 문제이므로 나는 다음과 같이 코드를 작성하였다.
sys.setrecursionlimit(100000)
sys.set_int_max_str_digits(100000)
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
def remove(num, k):
minNum = min(num)
left = num.index(minNum)
if len(num) == k:
return ''
if len(num[:left]) == k:
return num[left:]
if len(num[:left]) < k: #최소값의 위치보다 적게 있을 때
return num[left]+remove(num[left+1:], k-len(num[:left]))
if len(num[:left]) > k:
return remove(num[:left], k)+num[left:]
ans = remove(num, k)
return str(int(ans)) if ans!='' else "0" 오답 노트
실패의 원인
그런데 이 코드는num의 길이가 99999이고, k=50000일 때와 같은 edge case에서 반복적으로 함수를 호출하게 되면서 time limit exceed가 나왔다. 이 때 num은 반쯤은 1이 연속으로 붙어 있고, 나머지 반은 2가 연속으로 붙어있는 숫자여서, 최소값을 찾아도 그것의 인덱스는 늘 맨 앞일 것이고, 이 로직상으로는 len(num) == k가 나올 때까지, 즉 num의 길이가 50000이 될 때까지 재귀 호출을 49999번 하게 될 것이었다.
최솟값을 찾는 함수는 배열에 대해 O(n)의 시간이 걸리고, 배열이 정렬되어 있다면 최대 O(n)만큼 함수를 호출하게 되므로, 이 알고리즘은 O(n^2)의 시간 복잡도를 가지게 되면서 실패를 하게 된다.
min 함수를 아무 때나 쓰지 말자
더 효율적인 알고리즘
리트코드의 editorial에서 제시해 준 풀이는 monotonic stack을 활용하는 것이었다. num을 0 인덱스부터 n-1 인덱스까지 훑으면서 stack에 들어갈 수 있을지 여부를 검사한다. stack[-1]에 있는 수보다 i 인덱스의 수가 같거나 더 클 때 monotonic stack을 유지할 수 있다. 만약 stack[-1]의 값보다 더 작은 i 인덱스의 값이 나타난다면? 그 때는 i 인덱스의 수와 같거나 더 작은 수가 나타날 때까지 stack.pop()을 반복하면 된다. 그리고 k만큼 pop을 했다면 거기서부터 문제의 조건에 맞게 만들어질 수 있는 유일한 수 하나가 있는데 그것이 답이 된다.
사실 stack을 고려하지 않은 건 아닌데, 내가 두려워했던 어떤 상황은, index traversing을 하는 중에 '이미 stack에 k 이상의 수가 쌓여 있는데 갑자기 stack[-1]보다 작은 수가 나타났을 때'였다. '이미 뒤에 작은 수가 있는데 앞에 있는 것들을 지우는 것이 작은 수를 구하는 데 정말로 도움이 될까?!'와 같은 의심이 들었다. 그렇지만 monotonic stack 자료구조에서만큼은 stack.pop()만으로도 문제에서 요구하는 값을 구하는 데에는 도움이 된다.가장 작은 수들이 앞에 있음이 계속해서 유지되고 있기 때문이다. 이러한 알고리즘은 그리디 패턴에 해당한다고도 할 수 있을 것이다. 문제 풀이에서 그리디의 정신을 완전히 실현하지 못한 것을 통탄해하며.. 오늘도 하나 배워간다.
반성하면서 LeetCode 739를 연관 문제로 풀어보아야겠다.
