[리트코드][JAVA] 402. remove-k-digits (K 자리 제거)

💡 문제
remove-k-digits (https://leetcode.com/problems/remove-k-digits/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

1. 문자열 다루기

• 문자열 순회: 문자열을 문자 단위로 순회하면서 각 문자를 처리할 수 있어야 합니다.
• 문자열과 문자: 문자열을 문자 배열로 변환하거나, 각 문자에 접근하고 조작하는 방법을 알아야 합니다.

2. 스택 (Stack)

• 스택의 기본 연산: 스택은 LIFO(Last In First Out) 구조로 작동하는 자료구조입니다. 스택에서 요소를 추가하는 push와 제거하는 pop 연산을 이해해야 합니다.
• 스택을 이용한 문제 해결: 스택을 사용하면 현재 상태를 쉽게 추적하고, 필요 시 과거의 상태로 돌아갈 수 있습니다. 이 문제에서는 각 자리의 숫자를 스택에 넣고, 특정 조건에서 숫자를 제거하는 방식으로 문제를 해결합니다.

3. 그리디 알고리즘 (Greedy Algorithm)

• 그리디 알고리즘의 기본 개념: 그리디 알고리즘은 매 순간 최적의 선택을 하는 방법입니다. 이 문제에서는 가능한 한 작은 숫자를 만들기 위해 현재 자리에서 가장 작은 숫자를 선택하는 것이 최적의 선택이 됩니다.
• 문제 해결을 위한 그리디 접근: 현재 숫자보다 큰 숫자를 앞에서 제거함으로써 전체 숫자를 더 작게 만드는 방법을 적용합니다.

---

🤓 문제 풀이

🔨 문제 설명

주어진 숫자 문자열 num에서 k개의 숫자를 제거하여 가능한 가장 작은 숫자를 만들어야 합니다. 이때, 숫자의 순서는 유지되어야 하며, 결과 숫자에 불필요한 앞의 0이 없어야 합니다.

 

---

🔨 접근 방법

이 문제를 해결하기 위해서는 그리디 알고리즘과 스택을 사용하여 접근할 수 있습니다. 다음은 문제 접근 방법과 단계별 풀이 과정입니다:

• "Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num."
• 주어진 숫자 문자열에서 k개의 숫자를 제거하여 가능한 가장 작은 숫자를 반환해야 한다는 요구사항이 문제 접근의 기본입니다.
• 숫자 제거 개수 (k):
  • k개의 숫자를 제거해야 한다는 점이 문제의 핵심입니다.
  • 최대한 작은 숫자를 만들기 위해 어떤 숫자를 제거해야 할지 결정해야 합니다.
• 숫자 문자열 (num)의 순서 유지:
  • 숫자 순서를 유지해야 한다는 점에서 각 자릿수의 순회와 처리 방법을 생각해야 합니다.
• 가장 작은 숫자 만들기:
  • 숫자를 제거하여 가능한 가장 작은 숫자를 만들어야 합니다.
  • 이는 큰 숫자를 우선적으로 제거하는 것이 유리합니다.
• 불필요한 0 제거:
  • 결과 숫자에서 앞쪽의 불필요한 0을 제거해야 한다는 점도 중요합니다.

---

🔨 문제 풀이 과정

1. 스택 초기화:
   • 비어 있는 스택을 준비합니다.
   • 제거할 숫자의 개수를 나타내는 k를 준비합니다.
2. 숫자 순회 및 스택 처리:
   • 숫자 문자열 num을 왼쪽에서 오른쪽으로 한 자릿수씩 순회합니다.
   • 각 자릿수에 대해 다음 작업을 수행합니다:
     • 스택이 비어 있지 않고, 스택의 마지막 숫자가 현재 숫자보다 크고, k가 0보다 크면:
       • 스택의 마지막 숫자를 제거하고 k를 1 감소시킵니다.
     • 현재 숫자를 스택에 추가합니다.
3. 남은 숫자 처리:
   • 모든 자릿수를 순회한 후에도 k가 0보다 크면:
     • 스택의 끝에서부터 남은 k만큼 숫자를 제거합니다.
     • 순회가 끝난 후에도 k가 0이 되지 않았다면, 스택의 끝에서부터 남은 k만큼 숫자를 제거합니다.
4. 결과 생성 및 반환:
   • 스택에 남아 있는 숫자들을 차례대로 이어붙여 최종 결과 문자열을 만듭니다.
   • 결과 문자열의 앞에서부터 0을 제거합니다.
   • 결과 문자열이 빈 문자열이면 "0"을 반환합니다.

예제 풀이

예제 1:

• 입력: num = "1432219", k = 3
• 과정:
  1. 1을 스택에 추가: 스택 = [1]
  2. 4를 스택에 추가: 스택 = [1, 4]
  3. 3이 4보다 작고 k > 0, 4 제거: 스택 = [1], k = 2
  4. 3을 스택에 추가: 스택 = [1, 3]
  5. 2가 3보다 작고 k > 0, 3 제거: 스택 = [1], k = 1
  6. 2를 스택에 추가: 스택 = [1, 2]
  7. 2를 스택에 추가: 스택 = [1, 2, 2]
  8. 1이 2보다 작고 k > 0, 2 제거: 스택 = [1, 2], k = 0
  9. 1을 스택에 추가: 스택 = [1, 2, 1]
  10. 9를 스택에 추가: 스택 = [1, 2, 1, 9]
• 최종 스택: [1, 2, 1, 9]
• 결과 생성: "1219"

예제 2:

• 입력: num = "10200", k = 1
• 과정:
  1. 1을 스택에 추가: 스택 = [1]
  2. 0이 1보다 작고 k > 0, 1 제거: 스택 = [], k = 0
  3. 0을 스택에 추가: 스택 = [0]
  4. 2를 스택에 추가: 스택 = [0, 2]
  5. 0을 스택에 추가: 스택 = [0, 2, 0]
  6. 0을 스택에 추가: 스택 = [0, 2, 0, 0]
• 최종 스택: [0, 2, 0, 0]
• 결과 생성: "200" (앞의 0 제거)

예제 3:

• 입력: num = "10", k = 2
• 과정:
  1. 1을 스택에 추가: 스택 = [1]
  2. 0이 1보다 작고 k > 0, 1 제거: 스택 = [], k = 1
  3. 0을 스택에 추가: 스택 = [0]
  4. k가 1이므로 스택에서 1개 제거: 스택 = []
• 최종 스택: []
• 결과 생성: "0" (빈 문자열이므로 "0")

이런 식으로 주어진 숫자 문자열에서 k개의 숫자를 제거하여 가장 작은 숫자를 만들 수 있습니다.

---

🔨 문제 풀이 과정

문제에서 숫자가 문자열로 주어지는 이유는 숫자가 매우 클 수 있기 때문입니다. 105자리의 숫자를 일반적인 정수형 변수로 처리하는 것은 비효율적이거나 불가능할 수 있습니다. 문자열로 처리하면 이러한 큰 숫자도 각 자릿수를 쉽게 접근하고 조작할 수 있습니다.

그리디 알고리즘:

• 그리디 알고리즘은 현재 상태에서 가장 최선의 선택을 하는 방법입니다. 이 문제에서는 가능한 한 작은 숫자를 만들기 위해 큰 숫자를 제거하는 것이 최선의 선택입니다.

스택 사용:

• 스택은 LIFO (Last In, First Out) 구조로, 가장 최근에 추가한 요소를 먼저 제거할 수 있습니다. 이는 숫자 제거 문제에 매우 적합합니다.
• 스택을 사용하여 각 자릿수를 처리하면, 스택의 마지막 숫자와 현재 숫자를 비교하여 제거할지 말지를 결정할 수 있습니다.

---

🔨 구현코드

class Solution {
    public String removeKdigits(String num, int k) {
        // 스택을 사용하여 숫자를 관리
        Deque<Character> stack = new ArrayDeque<>();
        
        // 각 자릿수를 순회하며 스택에 추가 또는 제거
        for (char digit : num.toCharArray()) {
            while (!stack.isEmpty() && k > 0 && stack.peekLast() > digit) {
                stack.pollLast();
                k--;
            }
            stack.addLast(digit);
        }
        
        // 아직 제거해야 할 자릿수가 남아 있는 경우, 스택의 끝에서부터 제거
        while (k > 0) {
            stack.pollLast();
            k--;
        }
        
        // 스택에 남아 있는 자릿수들을 이용해 결과 문자열 생성
        StringBuilder result = new StringBuilder();
        boolean leadingZero = true;
        for (char digit : stack) {
            if (leadingZero && digit == '0') {
                continue; // 앞의 0 제거
            }
            leadingZero = false;
            result.append(digit);
        }
        
        // 결과가 비어 있는 경우 "0" 반환
        if (result.length() == 0) {
            return "0";
        }
        
        return result.toString();
    }
}

---

📚 풀이 보완

코드 설명

1. 스택 초기화:
   • Deque<Character>를 사용하여 스택을 초기화합니다.
   • 제거해야 할 숫자의 개수를 k로 설정합니다.
2. 숫자 순회 및 스택 처리:
   • num.toCharArray()를 사용하여 문자열의 각 자릿수를 순회합니다.
   • 현재 숫자가 스택의 마지막 숫자보다 작고 k가 남아 있다면, 스택의 마지막 숫자를 제거하고 k를 감소시킵니다.
   • 현재 숫자를 스택에 추가합니다.
3. 남은 숫자 처리:
   • 모든 숫자를 순회한 후에도 k가 남아 있으면, 스택의 끝에서부터 k개의 숫자를 제거합니다.
4. 결과 생성:
   • StringBuilder를 사용하여 스택에 남아 있는 숫자들을 이어 붙입니다.
   • 앞의 불필요한 0을 제거합니다.
   • 최종 결과가 빈 문자열이면 "0"을 반환합니다.

---

📍 Plus+

시간 복잡도

코드의 시간 복잡도는 주로 두 가지 부분에서 결정됩니다.

1. 숫자 순회:
   • for (char digit : num.toCharArray()): 문자열 num을 한 번 순회하며 각 자릿수를 처리합니다.
   • 이 루프의 시간 복잡도는 O(n)입니다. 여기서 n은 num의 길이입니다.
2. 스택 연산:
   • 각 자릿수를 스택에 추가하거나 제거할 때 while (!stack.isEmpty() && k > 0 && stack.peekLast() > digit) 조건을 확인합니다. 이 과정에서 최대 k번 숫자를 제거할 수 있습니다.
   • 각 숫자는 최대 한 번 스택에 추가되고 한 번 제거될 수 있습니다. 따라서 스택 연산의 총 시간 복잡도도 O(n)입니다.

따라서, 전체 시간 복잡도는 O(n)입니다.

공간 복잡도

• 스택: 최대 num의 길이만큼 숫자를 저장할 수 있습니다.
• 추가 변수: result라는 StringBuilder가 사용됩니다. 이는 결과 문자열을 저장하기 위한 것으로, 길이는 최대 num.length()와 같습니다.

따라서, 전체 공간 복잡도는 O(n)입니다. 여기서 n은 문자열 num의 길이를 의미합니다.

요약

• 시간복잡도: O(n)
• 공간복잡도: O(n)