문제 개요
음이 아닌 정수 num이 문자열 형태로 주어져 있다고 가정해 보겠습니다. 이 숫자에서 k개의 자릿수를 제거했을 때, 남은 숫자가 가능한 한 가장 작은 값이 되도록 만들어야 합니다.
예를 들어 입력이 "1432219"이고 k = 3이라면, 세 개의 자릿수를 적절히 제거한 결과는 "1219"가 됩니다.
접근 방법: 스택을 이용한 탐욕 알고리즘
이 문제는 스택(stack)과 탐욕(greedy) 기법을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 숫자를 왼쪽에서 오른쪽으로 하나씩 살펴보면서, 새로 등장한 숫자보다 큰 바로 앞자리 숫자를 제거하는 것입니다. 높은 자릿수의 큰 숫자를 없애는 것이 전체 값을 줄이는 데 가장 효과적이기 때문입니다.
알고리즘 단계
- 스택 st를 선언하고, 빈 문자열 ret을 생성합니다.
- n := num의 길이로 설정합니다.
- i를 0부터 n-1까지 반복합니다.
- k가 0이 아니고, 스택이 비어 있지 않으며, 스택의 top이 num[i]보다 큰 동안 스택에서 요소를 제거(pop)하고 k를 1씩 감소시킵니다.
- num[i]를 st에 삽입(push)합니다.
- 반복이 끝난 후에도 k가 0이 아니라면, 남은 k만큼 스택에서 요소를 계속 제거합니다.
- 스택이 빌 때까지 top 요소를 ret에 추가하면서 pop합니다.
- 스택 특성상 순서가 거꾸로 저장되므로 ret 문자열을 reverse()로 뒤집습니다.
- ans := 빈 문자열, i := 0으로 초기화합니다.
- ret의 맨 앞에 있는 불필요한 '0'(선행 0)을 모두 건너뜁니다.
- 남은 문자를 ans에 복사한 뒤 ret := ans로 갱신합니다.
- ret의 길이가 0이면 "0"을 반환하고, 그렇지 않으면 ret을 반환합니다.
C++ 구현 코드
더 나은 이해를 돕기 위해 전체 구현 코드를 살펴보겠습니다.
class Solution {
public:
string removeKdigits(string num, int k) {
stack<char> st;
string ret = "";
int n = num.size();
for(int i = 0; i < n; i++){
while(k && !st.empty() && st.top() > num[i]){
st.pop();
k--;
}
st.push(num[i]);
}
while(k--)st.pop();
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
string ans = "";
int i = 0;
while(i < ret.size() && ret[i] == '0')i++;
for(; i < ret.size(); i++)ans += ret[i];
ret = ans;
return ret.size() == 0 ? "0" : ret;
}
};실행 예시
입력
"1432219"
3
출력
"1219"
핵심 포인트 정리
- 탐욕적 선택: 현재 숫자보다 큰 직전 자릿수를 우선 제거하면 결과값이 최소화됩니다.
- 선행 0 처리: 제거 후 앞자리에 0이 남으면 모두 잘라내야 올바른 답이 됩니다.
- 예외 처리: 모든 자릿수가 제거된 경우 "0"을 반환합니다.
- 시간 복잡도: 각 문자가 최대 한 번 push되고 한 번 pop되므로 O(n)입니다. 여기서 n은 문자열의 길이입니다.