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

문자열S가 주어졌을 때, 같은 값의 이웃 문자를 제거하고 그 사이를 이어붙이는 동작을 반복하여서 빈 문자열로 만들 수 있는지 확인하는 문제.

처음에는 방문처리를 이용해 짝이 더이상 생기지 않을때까지 문자열의 모든 원소를 짝검사 하는 방식으로 접근했다. S의 길이는 최대 1,000,000이었는데 구현한 방법은 $O(N^2)$이었으므로 TLE가 나왔다.

잘 고민해보니 괄호 유효성 검사와 비슷한 구조인게 보여서 스택으로 해결할 수 있었다.

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

cpp code

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

int solution(string s)
{
    stack<int> S;
    for (int i=0;i<s.length();i++) {
        if (S.empty()) {
            S.push(s[i]);
            continue;
        }
        if (s[i] == S.top()) S.pop();
        else S.push(s[i]);
    }
    return S.empty();
}