💡 문제
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을 제거해야 한다는 점도 중요합니다.
🔨 문제 풀이 과정
- 스택 초기화:
- 비어 있는 스택을 준비합니다.
- 제거할 숫자의 개수를 나타내는 k를 준비합니다.
- 숫자 순회 및 스택 처리:
- 숫자 문자열 num을 왼쪽에서 오른쪽으로 한 자릿수씩 순회합니다.
- 각 자릿수에 대해 다음 작업을 수행합니다:
- 스택이 비어 있지 않고, 스택의 마지막 숫자가 현재 숫자보다 크고, k가 0보다 크면:
- 스택의 마지막 숫자를 제거하고 k를 1 감소시킵니다.
- 현재 숫자를 스택에 추가합니다.
- 스택이 비어 있지 않고, 스택의 마지막 숫자가 현재 숫자보다 크고, k가 0보다 크면:
- 남은 숫자 처리:
- 모든 자릿수를 순회한 후에도 k가 0보다 크면:
- 스택의 끝에서부터 남은 k만큼 숫자를 제거합니다.
- 순회가 끝난 후에도 k가 0이 되지 않았다면, 스택의 끝에서부터 남은 k만큼 숫자를 제거합니다.
- 모든 자릿수를 순회한 후에도 k가 0보다 크면:
- 결과 생성 및 반환:
- 스택에 남아 있는 숫자들을 차례대로 이어붙여 최종 결과 문자열을 만듭니다.
- 결과 문자열의 앞에서부터 0을 제거합니다.
- 결과 문자열이 빈 문자열이면 "0"을 반환합니다.
예제 풀이
예제 1:
- 입력: num = "1432219", k = 3
- 과정:
- 1을 스택에 추가: 스택 = [1]
- 4를 스택에 추가: 스택 = [1, 4]
- 3이 4보다 작고 k > 0, 4 제거: 스택 = [1], k = 2
- 3을 스택에 추가: 스택 = [1, 3]
- 2가 3보다 작고 k > 0, 3 제거: 스택 = [1], k = 1
- 2를 스택에 추가: 스택 = [1, 2]
- 2를 스택에 추가: 스택 = [1, 2, 2]
- 1이 2보다 작고 k > 0, 2 제거: 스택 = [1, 2], k = 0
- 1을 스택에 추가: 스택 = [1, 2, 1]
- 9를 스택에 추가: 스택 = [1, 2, 1, 9]
- 최종 스택: [1, 2, 1, 9]
- 결과 생성: "1219"
예제 2:
- 입력: num = "10200", k = 1
- 과정:
- 1을 스택에 추가: 스택 = [1]
- 0이 1보다 작고 k > 0, 1 제거: 스택 = [], k = 0
- 0을 스택에 추가: 스택 = [0]
- 2를 스택에 추가: 스택 = [0, 2]
- 0을 스택에 추가: 스택 = [0, 2, 0]
- 0을 스택에 추가: 스택 = [0, 2, 0, 0]
- 최종 스택: [0, 2, 0, 0]
- 결과 생성: "200" (앞의 0 제거)
예제 3:
- 입력: num = "10", k = 2
- 과정:
- 1을 스택에 추가: 스택 = [1]
- 0이 1보다 작고 k > 0, 1 제거: 스택 = [], k = 1
- 0을 스택에 추가: 스택 = [0]
- 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();
}
}
📚 풀이 보완
코드 설명
- 스택 초기화:
- Deque<Character>를 사용하여 스택을 초기화합니다.
- 제거해야 할 숫자의 개수를 k로 설정합니다.
- 숫자 순회 및 스택 처리:
- num.toCharArray()를 사용하여 문자열의 각 자릿수를 순회합니다.
- 현재 숫자가 스택의 마지막 숫자보다 작고 k가 남아 있다면, 스택의 마지막 숫자를 제거하고 k를 감소시킵니다.
- 현재 숫자를 스택에 추가합니다.
- 남은 숫자 처리:
- 모든 숫자를 순회한 후에도 k가 남아 있으면, 스택의 끝에서부터 k개의 숫자를 제거합니다.
- 결과 생성:
- StringBuilder를 사용하여 스택에 남아 있는 숫자들을 이어 붙입니다.
- 앞의 불필요한 0을 제거합니다.
- 최종 결과가 빈 문자열이면 "0"을 반환합니다.
📍 Plus+
시간 복잡도
코드의 시간 복잡도는 주로 두 가지 부분에서 결정됩니다.
- 숫자 순회:
- for (char digit : num.toCharArray()): 문자열 num을 한 번 순회하며 각 자릿수를 처리합니다.
- 이 루프의 시간 복잡도는 O(n)입니다. 여기서 n은 num의 길이입니다.
- 스택 연산:
- 각 자릿수를 스택에 추가하거나 제거할 때 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)