[LeetCode] 402 Remove K Digits(Java)

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. 마치며

이 문제는 단순히 숫자를 제거하는 것이 아니라, **"어떤 시점에 제거해야 최적인가"**를 결정하는 그리디 전략이 핵심입니다. 단조 스택의 원리를 이해하고 있다면 다양한 유사 문제(예: 가장 큰 수 만들기 등)에 응용할 수 있는 좋은 예제였습니다.