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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

가장 단순한 풀이는 문자열 처음부터 연속된 문자들을 찾고, 이를 문자열에서 제거하는 과정을 반복하는 것이다.

하지만, 스택을 이용하면 문자열을 한번만 순회하고도 연속된 문자들을 짝지어 제거할 수 있다.

 

결론적으로, 문자들을 하나씩 스택에 넣되,  만약 가장 최근에 스택에 들어간 문자(top에 있는 문자)가 현재 넣으려는 문자와 같다면 이는 연속된 것이므로 바로 제거하면 된다.

 

예를 들어, 빈 스택 st 이 있고, 문자열이 "baabaa" 라 해보자.

b -> 스택이 비었으므로 그냥 b 넣기(스택 상태: b)

a -> top에 있는 문자가 b이므로 그냥 a 넣기(스택 상태: ba)

a -> top에 있는 문자가 a이므로 연속되는 문자 제거(스택 상태: b)

b -> top에 있는 문자가 b이므로 연속되는 문자 제거(스택 상태: 비어있는 스택)

a -> 스택이 비었으므로 그냥 a 넣기(스택 상태: a)

a -> top에 있는 문자가 a이므로 연속되는 문자 제거(스택 상태: 비어있는 스택)

 

결과 스택이 비어있다면, 모든 문자가 제거된 것이므로 1을 리턴한다.

스택에 문자가 남아있을 때, 제거되지 않은 문자가 있는 것이므로 0을 리턴한다.

 

여는 괄호와 닫는 괄호를 짝짓는 문제, 문자들을 짝짓는 문제는 스택을 활용한 기본 문제이므로 잘 알아두자!

 

 

코드

 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(string s) {
    stack<char> st;
    for (auto c : s) {
        if (!st.empty() && st.top() == c) st.pop();
        else st.push(c);
    }
    return (int)st.empty();
}