문제 개요
소문자 알파벳으로만 이루어진 문자열이 주어졌을 때, 모든 중복 문자를 제거하여 각 문자가 정확히 한 번만 나타나도록 만들어야 합니다. 이때 결과 문자열은 가능한 한 사전순(lexicographic)으로 가장 작은 순서가 되어야 합니다.
예를 들어 입력이 "abccb"라면, 각 문자를 한 번씩만 포함하면서 사전순으로 가장 작은 결과인 "abc"를 반환해야 합니다.
해결 접근 방법
이 문제는 스택(stack), 빈도 카운트 맵, 스택 포함 여부 배열을 활용한 그리디 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 처리 중인 문자가 스택 top에 있는 문자보다 사전순으로 작고, top의 문자가 뒤에 다시 등장할 예정이라면 top을 제거해도 됩니다.
- 이미 스택에 있는 문자라면 건너뛰어 중복을 방지합니다.
알고리즘 단계
- 결과를 담을 빈 문자열
ans와 빈 스택st를 준비합니다. - 각 알파벳의 스택 포함 여부를 추적할 크기 26의 배열
onStack을 선언합니다. - 문자별 남은 개수를 저장할 맵
m을 만듭니다. - 첫 번째 순회에서 각 문자의 등장 횟수를
m에 카운트합니다. - 두 번째 순회에서 각 문자
x = s[i]에 대해 다음을 수행합니다.m[x]를 감소시켜 남은 등장 횟수를 갱신합니다.x가 이미 스택에 있다면(onStack[x - 'a']이 참) 다음 문자로 넘어갑니다.- 스택이 비어 있지 않고, 현재 문자
x가 top보다 작으며, top의 문자가 뒤에 더 등장한다면(m[st.top()] > 0) top을 제거하고 해당 문자의 onStack 플래그를 해제합니다. x를 스택에 넣고onStack[x - 'a']를 참으로 설정합니다.
- 마지막으로 스택의 모든 원소를 꺼내
ans에 붙인 뒤, 뒤집어서 반환합니다. (스택은 LIFO이므로 역순으로 쌓여 있습니다.)
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicateLetters(string s) {
string ans = "";
stack<char> st;
vector<int> onStack(26);
map<char, int> m;
int n = s.size();
for(int i = 0; i < n; i++){
m[s[i]]++;
}
for(int i = 0; i < n; i++){
char x = s[i];
m[x]--;
if(onStack[x - 'a'])
continue;
while(!st.empty() && x < st.top() && m[st.top()]){
onStack[st.top() - 'a'] = false;
st.pop();
}
st.push(x);
onStack[x - 'a'] = true;
}
while(!st.empty()){
char x = st.top();
st.pop();
ans += x;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
int main(){
Solution ob;
cout << ob.removeDuplicateLetters("abccb");
}입력
"abccb"
출력
"abc"
동작 원리 설명
입력 "abccb"를 단계별로 살펴보면 다음과 같습니다.
a처리: 스택이 비어 있으므로 push → 스택:[a]b처리:b > a이므로 그대로 push → 스택:[a, b]c처리:c > b이므로 그대로 push → 스택:[a, b, c]c처리: 이미 스택에 있으므로 건너뜁니다.b처리: 이미 스택에 있으므로 건너뜁니다.
최종적으로 스택을 꺼내 역순으로 연결하면 "abc"가 되며, 이것이 사전순으로 가장 작은 유효한 결과입니다.
시간 복잡도 분석
각 문자는 최대 한 번 push되고 한 번 pop되므로, 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 또한 스택, 맵, onStack 배열에 의해 O(n)입니다.