728x90
반응형
1. 문제 설명
문제 링크: LeetCode 402 - Remove K Digits
요약: 주어진 숫자 문자열 num에서 k개의 숫자를 제거하여 만들 수 있는 가장 작은 수를 구하는 문제입니다. 결과값에서 앞자리에 오는 0은 제거해야 하며, 빈 문자열이 될 경우 "0"을 리턴해야 합니다.
2. 핵심 아이디어
가장 작은 수를 만들기 위해서는 앞자리에 최대한 작은 숫자가 위치해야 합니다. 이를 위해 그리디(Greedy) 알고리즘과 단조 증가 스택(Monotonic Stack) 논리를 활용합니다.
- 비교와 제거: 숫자를 순차적으로 확인하며, 현재 숫자보다 바로 앞의 숫자가 더 크다면 앞의 숫자를 제거합니다. 이 과정을 k번 반복하여 큰 숫자가 앞자리에 오지 못하게 막습니다.
- 스택의 활용: StringBuilder를 스택처럼 사용하여 마지막에 추가된 숫자와 현재 숫자를 비교합니다.
- 잔여 k 처리: 만약 숫자가 "1234"와 같이 계속 증가하는 형태라 루프 내에서 제거되지 않았다면, 남은 k만큼 뒤에서부터 잘라냅니다.
- 예외 처리: "0012"와 같은 결과에서 앞의 '0'들을 제거하고, 모든 숫자가 사라진 경우 "0"을 반환합니다.
3. 코드
Java
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder sb = new StringBuilder();
// 1. 그리디 탐색: 현재 숫자보다 큰 이전 숫자는 제거
for (char c : num.toCharArray()) {
while (k > 0 && sb.length() > 0 && sb.charAt(sb.length() - 1) > c) {
sb.deleteCharAt(sb.length() - 1);
--k;
}
sb.append(c);
}
// 2. 남은 k 처리: 숫자가 계속 증가하는 형태일 경우 뒤에서 제거
while (k > 0) {
sb.deleteCharAt(sb.length() - 1);
k--;
}
// 3. 앞자리 0 제거
while (sb.length() > 0 && sb.charAt(0) == '0') {
sb.deleteCharAt(0);
}
// 4. 빈 문자열 처리
if (sb.length() == 0) {
sb.append('0');
}
return sb.toString();
}
}
4. 코드 포인트 해설
- sb.charAt(sb.length() - 1) > c: 현재 문자 c가 이전 문자보다 작다면, 이전 문자를 제거하는 것이 전체 수의 크기를 줄이는 최선의 선택입니다.
- StringBuilder의 효율성: 별도의 Stack<Character> 클래스를 사용하는 것보다 StringBuilder를 직접 조작하는 것이 객체 생성 비용을 줄이고 마지막에 문자열로 변환하기에 훨씬 유리합니다.
- 선행 0 제거: while (sb.charAt(0) == '0') 루프를 통해 숫자의 유효성을 확보합니다.
5. 성능 및 복잡도
- 시간 복잡도: 문자열의 길이를 $N$이라 할 때, 각 문자는 최대 한 번 스택에 추가되고 한 번 제거됩니다. 따라서 **$O(N)$**의 선형 시간에 해결됩니다.
- 공간 복잡도: 결과를 저장하고 조작하기 위한 공간으로 **$O(N)$**을 사용합니다.
6. 마치며
이 문제는 단순히 숫자를 제거하는 것이 아니라, **"어떤 시점에 제거해야 최적인가"**를 결정하는 그리디 전략이 핵심입니다. 단조 스택의 원리를 이해하고 있다면 다양한 유사 문제(예: 가장 큰 수 만들기 등)에 응용할 수 있는 좋은 예제였습니다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
| [알고리즘 기법] 백트랙킹(Back-Tracking) (0) | 2026.03.19 |
|---|---|
| [LeetCode] 51 N-Queens(Java) (0) | 2026.03.18 |
| [LeetCode] 1775 Closest Dessert Cost(Java) (0) | 2026.03.16 |
| [백준] BOJ 2979 트럭 주차(Java) (0) | 2026.03.14 |
| [백준] BOJ 10808 알파벳 개수(Java) (0) | 2026.03.13 |