짝지어 제거하기 (feat. 프로그래머스, 12973번)

짝지어 제거하기
https://programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

반응형

// woohyeon.kim
#include <string>
#include <stack>
#include <iostream>
using namespace std;

int solution(string s)
{
    stack<char> q;
    for(const auto& c : s)
    {
        if(!q.empty())
        {
            if(q.top() == c)
                q.pop();
            else
                q.push(c);
        }
        else
            q.push(c);
    }
    return q.empty() ? 1 : 0;
}
// *&)*@*

후입선출 구조인 stack을 아신다면 쉽게 풀수 있습니다. (물론 문제를 보자마자 생각나면 코테를 위한 코더일 확률이...)

만약 string을 그대로 하면서 position을 계산하고 erase하는 방식으로 한다면, 시간초과가 날 확률이 높습니다.

​

queue는 선입선출 구조입니다. 즉, 비교 후 같으면 pop을 해야 하는데, queue는 가장 마지막에 들어간 아이가 아닌 가장 처음에 들어간 아이가 나옵니다. 따라서 stack으로 해결할 수 있습니다.