[프로그래머스] 2단계 - 짝지어 제거하기

문제 설명

문자열에서 같은 알파벳이 2개 붙어있는 짝을 제거한 뒤, 앞 뒤로 문자열을 이어붙이는 과정을 반복하면서 문자열을 모두 제거가 가능한지 여부를 return

 

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

프로그래머스

 

문제 풀이법

먼저 string의 erase 함수를 사용해서 문제를 풀었었다

하지만 답은 맞지만, 효율성 테스트에서 전부 실패를 했기에 좀 더 빠른 방법을 찾아서 stack을 사용하게 되었다

 

문자열을 순회하며 stack이 비었거나, 해당 문자열의 문자가 stack의 top과 다르면 push 한다

만일 stack의 top과 문자열의 문자가 같으면 pop 한다

 

문자열의 모든 문자를 다 본 후 stack에 값이 남아있으면 문자열을 모두 제거할 수 없으므로 0을 반환하고, 그렇지 않으면 1을 반환한다 

 

소스 코드

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

int solution(string s)
{
    int answer = -1;
    stack<char> st;
    
    for (int i = 0; i < s.size(); i++) {
        if (st.empty() || st.top() != s[i])
            st.push(s[i]);
        else if (st.top() == s[i])
            st.pop();
    }
    
    if (st.empty())
        answer = 1;
    else
        answer = 0;

    return answer;
}