짝지어 제거하기

코드

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

int solution(string s)
{
    int answer = 0;
    stack<int> sta;
    int i=1;
    sta.push(s[0]);
    while(i < s.length())
    {
        if(!sta.empty() && s[i] == sta.top()){
            sta.pop();
            i++;
        }else sta.push(s[i++]);
    }
    if(sta.empty()) answer = 1;
    else answer =0;
    return answer;
}

• 단순히 string에서 삭제하는 방식으로 하면 --> O(N^2)
• 효율성과 관련한 문제에 부딛히면 '자료구조'를 바꾸는 것을 생각해보기!
• 이전 값과 현재 값의 상관관계가 있는 경우 stack을 고려해보자!