[알고리즘C++]짝지어 제거하기

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/12973

짝지어 제거하기

나의 풀이

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

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

모범 답안

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

int solution(string s)
{
    stack <char> g;
    int stack_size=0;
    for(int i=0;i<s.length();i++){
        if(stack_size>0&&g.top()==s[i]){g.pop();stack_size--;}
        else{g.push(s[i]);stack_size++;}
    }
    return (stack_size==0);
}

배울 점

• 그냥 순서대로 비교는 시간초과가 나서 한번 더 생각해보니 stack을 이용하면 되더라
• 시간초과가 날 것을 잘 생각해야한다