문제 설명
문자열 s가 주어졌을 때, 'k 중복 제거'는 문자열에서 인접하면서 서로 같은 문자 k개를 선택하여 삭제하는 연산을 의미합니다. 삭제된 부분 문자열의 왼쪽과 오른쪽은 자동으로 이어 붙여집니다. 이러한 k 중복 제거를 더 이상 문자열을 변경할 수 없을 때까지 반복 수행한 뒤, 최종 결과 문자열을 구하는 것이 목표입니다.
예를 들어 s = "deeedbbcccbdaa", k = 3이라고 가정해 보겠습니다.
- 먼저 "eee"와 "ccc"를 삭제하면 → "ddbbbaa"
- 다음으로 "bbb"를 삭제하면 → "dddaa"
- 마지막으로 "ddd"를 삭제하면 → "aa"
따라서 최종 출력은 "aa"가 됩니다.
알고리즘 접근 방법
이 문제는 스택(Stack)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 문자와 해당 문자가 연속으로 등장한 횟수를 함께 저장하는 것입니다.
- 결과를 담을 빈 문자열 ans를 준비합니다.
- (문자, 개수) 쌍을 저장할 스택을 생성하고, n을 문자열의 길이로 설정합니다.
- i를 0부터 n까지 순회하면서 다음을 수행합니다.
- x := s[i]
- 스택이 비어 있지 않고 스택 top의 개수가 k와 같으면, 해당 요소를 pop합니다.
- i == n이면 반복을 종료합니다.
- 스택이 비어 있거나 스택 top의 문자가 x와 다르면 (x, 1) 쌍을 push하고 i를 1 증가시킵니다.
- 그렇지 않으면 스택 top의 개수를 1 증가시키고 i를 1 증가시킵니다.
- 스택이 빌 때까지 다음을 반복합니다.
- temp := 스택 top 요소
- temp의 개수가 0이 될 때까지 ans에 temp의 문자를 추가합니다.
- 스택에서 top 요소를 pop합니다.
- ans 문자열을 뒤집어 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans = "";
stack < pair<char, int> > st;
int n = s.size();
for(int i = 0; i <= n;){
char x = s[i];
if(!st.empty() && st.top().second == k)st.pop();
if(i == n)break;
if(st.empty() || st.top().first != x){
st.push({x, 1});
i++;
} else {
st.top().second++;
i++;
}
}
while(!st.empty()){
pair <char, int> temp = st.top();
while(temp.second--) ans += temp.first;
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3));
}입력
"deeedbbcccbdaa" 3
출력
aa
복잡도 분석
- 시간 복잡도: O(n) — 문자열의 각 문자를 한 번씩만 처리합니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 문자가 스택에 저장될 수 있습니다.