문제 이해하기
문자열 "abc"가 유효(valid)하다고 가정해 봅시다. 임의의 유효한 문자열 V를 두 조각 X와 Y로 나눌 수 있고(X 또는 Y는 비어 있어도 됨), X + Y가 V와 같다면 X + "abc" + Y 역시 유효한 문자열이 됩니다.
예를 들어 유효한 문자열에는 "abc", "aabcbc", "abcabc", "abcabcababcc" 등이 있으며, 유효하지 않은 문자열에는 "abccba", "ab", "cababc", "bac" 등이 있습니다. 우리가 할 일은 주어진 문자열 S가 유효한지 여부를 판별하는 것입니다.
예를 들어 입력이 "abcabcababcc"라면 이 문자열은 유효하므로 결과는 true가 됩니다.
해결 접근 방법
스택(Stack) 자료구조를 활용하면 이 문제를 효율적으로 해결할 수 있습니다. 핵심 아이디어는 문자를 하나씩 스택에 쌓다가 'c'를 만날 때마다 스택 위 세 글자가 "abc"를 이루는지 확인하고, 이루고 있다면 해당 세 글자를 제거(치환 완료)하는 것입니다. 알고리즘 단계는 다음과 같습니다.
- 스택 st를 정의합니다.
- i를 0부터 S의 길이까지 반복합니다.
- 스택이 비어 있거나 S[i]가 'c'가 아니면 S[i]를 스택에 push합니다.
- S[i]가 'c'라면:
- 'c'를 스택에 삽입합니다.
- 스택의 크기가 3 이상인 동안 다음을 반복합니다.
- c := 스택의 최상단(top) 요소를 꺼내고(pop) 저장합니다.
- b := 스택의 최상단 요소를 꺼내고 저장합니다.
- a := 스택의 최상단 요소를 꺼내고 저장합니다.
- temp := a, b, c를 차례대로 이어 붙입니다.
- temp가 "abc"와 같다면 다음 반복으로 진행합니다(세 글자 성공적으로 제거).
- 그렇지 않다면 a, b, c 순서대로 다시 스택에 push하고 내부 반복을 종료합니다.
- 모든 문자를 처리한 후 스택이 비어 있으면 true, 그렇지 않으면 false를 반환합니다.
스택이 완전히 비워졌다는 것은 모든 문자가 "abc" 단위로 정확히 소비되었다는 의미이므로, 이것이 곧 유효성 판별의 기준이 됩니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isValid(string S) {
stack <char> st;
for(int i = 0; i < S.size(); i++){
if(st.empty() || S[i] != 'c'){
st.push(S[i]);
}else{
st.push('c');
while(st.size() >= 3){
char c = st.top();
st.pop();
char b = st.top();
st.pop();
char a = st.top();
st.pop();
string temp = "";
temp += a;
temp += b;
temp += c;
if(temp == "abc"){
continue;
}else{
st.push(a);
st.push(b);
st.push(c);
break;
}
}
}
}
return st.empty();
}
};
main(){
Solution ob;
cout << (ob.isValid("abcabcababcc"));
}입력
“abcabcababcc”
출력
1
복잡도 분석
각 문자는 최대 한 번 push되고, "abc" 매칭 과정에서 다시 push되는 경우도 있지만 전체적으로 각 문자당 상수 번의 연산만 수행되므로 시간 복잡도는 O(n)입니다. 스택에는 최대 입력 문자열 길이만큼의 문자가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다.