LeetCode Remove K Digits

작성일 | In |

Problem : Remove K Digits

유형 : 스택

문제 해석

  • 문자열로 표현된 숫자가 들어오면, 그 중 K개를 제거해 최소의 수를 만들어라.

문제 재해석

  • 3자리수가 들어오고 3개가 제거되면 0을 리턴해야한다.
  • 0200은 0이 제거된 200으로 표현 되어야한다.
  • 문자열의 길이는 10002이다. O(n^2) 이하로 해결하려고 했다.

해결 전략

  • 가장 작은 수를 만드는 경우를 어떻게 만들 수 있을까를 생각해보았다.
  • 19의 경우 9를 제거하면 가장 작은 수인 1이 된다.
  • 그러면 가장 큰 숫자를 제거하면 될까? 아니다.
  • 219의 경우 9를 제거하면 21이지만 2를 제거하면 19가 된다.
  • 큰 자리수부터 작은 자리로 순차적으로 접근한다.
  • 큰 자리수의 숫자보다, 작은 자리수의 숫자가 작아지는 경우에 대해서 큰 자리수를 제거해준다.

설계, 구현

  • 순차적으로 탐색하고, 인접한 것들의 관계를 고려하므로 스택을 이용해 구현했다.
  • "01" 과 같이 끝나는 경우를 방지하기 위해서, 가장 앞자리가 "0"이 되는 경우는 스택에 아예 넣지 않았다.
  • 가장 큰 자리 수 부터 확인한다. 234 이라면, 100의 자리수 인 2부터 확인한다.
  • 스택의 top보다 작은 숫자를 만난경우, pop 한다.
    • 315 의 경우 1는 3보다 작으니 3을 제거한다
    • 132 의 경우 2는 3 보다 작으니 3을 제거한다
    • 2331 의 경우, 33을 제거한다.
  • k개를 아직 제거하지 못했다면 pop한다

주의할점

  • 문자열의 길이가 10002가 될 수 있다.
  • 문자열 > 숫자 > 문자열을 시도시 오버플로우가 날 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans = "";
        for (const char &n : num) {
            while (!ans.empty() and n < ans.back() and k > 0) {
                ans.pop_back();
                k--;
            }
            if (ans.empty() and n == '0') continue;
            ans.push_back(n);
        }
        while (!ans.empty() and k > 0) {
            ans.pop_back();
            k--;
        }
        if (ans.empty()) return "0";
        return ans;
    }
};

피드백

  • 과거 풀어보았던 문제를 다시 보면서 포스팅해봤다.
  • 릿코드 문제가 전체적으로 괜찮았다는 기억이 다시한번 떠올랐다.
  • 하반기에도 취준을 하게 된다면 릿코드도 많이 풀어볼 생각이다.