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

https://school.programmers.co.kr/learn/courses/30/lessons/12973?language=cpp 

프로그래머스

전체 코드

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

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

 

스택을 이용해 푼다. 만약 아래와 같이 for문을 이용해 푼다면 시간 초과가 난다.

    /*for(int i=1;i<s.length();i++)
    {
        if(s[i]==s[i-1])
        {
            s.erase(s.begin()+i-1,s.begin()+i+1);
            i-=2;
        }
    }*/

 

스택에 push하는 경우는 스택이 비어있거나, 스택 원소와 s[i]와 다를 때 s[i]를 넣는다.

스택에 pop하는 경우는 s[i]와 스택의 원소가 같을 때 pop을 해준다.

for문을 돌고난뒤 스택에 남아있다면 완전히 제거하지 못한것이다.

 

스택을 이용하면 시간 복잡도 n으로 문제를 해결할 수 있다.

 

시간 초과가 나는 코드 같은 경우는 "abcdefghijklmnopqrstuvwz+zwvutsr...cba"처럼 극단적인 경우가 있기에 초과가 난다.

스택을 이용하면 어떤 경우도 n번의 탐색으로 해결이 가능하다.