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

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

코딩테스트 연습 - 짝지어 제거하기

[해결방법]

단순히 계속 반복 비교하면 효율성을 통과하지 못한다.

stack 을 사용하자

1. 스택이 비어있다면 push

2. 스택의 top 과 일치한다면 스택의 top 을 pop

3. 스택의 top 과 일치하지 않는다면 push

4. 모든게 일치할 경우, 스택은 빈다. 따라서 리턴 1

5. 스택이 비지 않았을 경우 리턴 0

cur	top
b	b (new)
a	a (new)	b
a	a(x)	b
b	b(x)
a	a (new)
a	a(x)

 

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

stack <char> st;

int solution(string s)
{

    for(int i=0; i<s.size(); i++) {
        if(st.empty())
            st.push(s[i]);

        else if(st.top() == s[i])
            st.pop();
        else 
            st.push(s[i]);
    }

    if(st.size() == 0)
        return 1;
    return 0;
}