stack을 활용한 제거 시뮬레이션.
stack을 2개 사용하여 뚜껑과 밑통으로 활용하고
각 stack의 top을 비교대상으로 삼았다.
일치하면 각 stack을 pop하여 새로운 top들이 탄생하고
일치하지 않으면 바닥 stack top이 뚜껑 stack으로 이동한다.
마지막에 전부 없앨 수 있는지의 여부는 뚜껑 stack이 비어있는가를 사용했다.
왜냐면 뚜껑 stack의 경우 붙어있는 원소들끼리 일치하는 경우는 없기 때문이다.
pop 연산을 해가며 제거된 문자열을 압축하는 방법.
편하다. 빈공간이 생기는 것에 대한 걱정이 없음
pop 연산에 O(N)이 발생한다. => O(N^2)
pop 연산을 하며 문자열을 압축하는 것 대신 ' '문자로 채움으로써 사라진 문자임을 표시.
같은지 비교하는 위치 i(앞에거) j(뒤에거) 가 총 길이가 변하지 않으니가 움직이는 걸 좀 더 안정적으로 구현할 수 있다.
이미 지워진 자리 ' '를 만났을 때...
b__a__ab 에서 a들끼리 지워진 후 b______b 가되어 b들끼리 지워져야한다.
j의 경우 내가 지우지 못한 방향으로 가니까 그냥 산술적으로 커지면 되지만
i의 경우 내가 지웠던 부분들을 건너 뛰어야 하기(나는 while문을 사용했다.) 때문에 O(N)이 발생한다.
정답을 받기까지 2시간 정도 소요됐다.
#include <iostream>
#include<stack>
using namespace std;
string stack_to_str(stack<char> s){
string ret = "";
while(!s.empty()){
ret+=s.top();
s.pop();
}
return ret;
}
int solution(string str)
{
int answer = 0;
//문제와의 지우는 순서 일치를 위해 거꾸로 넣기
stack<char> q;
for(int i = str.size()-1;i>=0;i--){
q.push(str[i]);
}
stack<char> sq;//subq
while(!q.empty()){
if(!sq.empty()){
char a = sq.top();
char b = q.top();
//cout<<"검사중! "<<a<<" , "<<b<<endl;
if(a == b){
sq.pop();
q.pop();
}
else{
q.pop();
sq.push(b);
}
}
else{
int o = q.top();
q.pop();
sq.push(o);
}
/*
cout<<stack_to_str(q)<<endl;
cout<<stack_to_str(sq)<<endl;
cout<<"=================="<<endl;
*/
}
if(sq.empty()){
answer = 1;
}
return answer;
}