[프로그래머스/C++] 짝지어 제거하기

✅ LV.2

📌 2017 팁스타운

✏️ 1차 솔루션

모든 문자가 사라질 때까지 while문 돌면서 연속되는 문자 있는지 확인
연속되는 문자가 있으면 erase 함수 사용해서 해당 두 문자를 지우기
연속문자 유무 체크해서 for문 돌았는데 연속문자가 없었다면 더 이상 제거할 수 없는 것이므로 answer 값을 0으로 정하고 while문 break

🚨 1차 trouble

효율성 통과 못함
while문에 for문 써서 시간초과난 듯

✏️ 최종 솔루션

⭐️ stack 사용
for 문으로 모든 자리를 돌면서 스택에 저장해서 연속 문자를 색출
1) stack에 문자를 계속 push하면 앞 자리 문자가 top 에 있기 때문에 top 과 현재 자리를 비교해서 같은 문자면 top 을 pop 해서 연속 문자를 삭제
➡️ 이렇게 하면 삭제한 다음 문자부터는 삭제 이전 문자와 바로 비교 가능
2) 연속 문자가 아니면 현재 문자를 stack 에 push 해서 비교 이어나가도록 함

📌 self feedback

stack을 사용해서 문자열을 삭제할 때마다 처음부터 문자열을 반복 탐색할 필요가 없어서 시간복잡도를 줄일 수 있었음

✏️ 최종 code

#include <iostream>
#include<string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = 1;

    stack<char> st;
    st.push(s[0]);
    for(int i=1;i<s.size();i++) {
        if(st.empty() || s[i]!=st.top()) st.push(s[i]);
        else st.pop();
    }
    
    if(!st.empty()) answer=0;

    return answer;
}