2017 팁스타운 - 짝지어 제거하기

[문제 원본]코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스 (programmers.co.kr)

괄호 문제, 짝 짓는 문제 등은 보통 Stack으로 풀릴 때가 많습니다.

같은 문자가 반복되는 짝을 계속하여 제거하였을 때, 모두 제거가 되는지 판단하는 문제입니다.
아래와 같은 논리로 접근하시면 됩니다.

• 문자열이 홀수인 경우 모두 짝을 지어도 1개는 꼭 남기때문에 바로 0을 return
• 짝을 판단할 stack 생성 (STL의 stack 컨테이너 사용)
• 문자열의 처음부터 iterator를 증가시켜가며 진행합니다.

  Stack이 비었을 경우

• Stack이 비었을 경우 현재 가리키고 있는 문자를 push

Stack이 비어있지 않은 경우

• Stack의 top과 비교하였을 때 일치하면 pop으로 제거 (짝 지어짐)
• 일치하지 않으면 push로 stack에 담기

문자열의 길이만큼 Iteration 후 stack이 비어있는지를 return하면 됩니다.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int solution(string s) {
    if (s.size() % 2)
        return 0;

    stack<char> st;

    for (auto it = s.begin(); it != s.end(); ++it) {
        if (st.empty() || st.top() != *it)
            st.push(*it);
        else
            st.pop();
    }
    return st.empty();
}