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

 이 문제는 스택을 이용하는 문제이다. 주어진 문자열을 순차 탐색하면서 스택에 push하거나 pop 하므로, O(n) 시간이 걸리는데 문자열의 최대 길이가 1,000,000 이므로 충분히 시간 안에 풀 수 있다.

 

 스택을 이용했을 때 top과 비교해서 현재 문자가 같으면 pop, 다르면 push 하고, 전체 탐색이 끝난 후 스택에 문자가 남아있으면 0, 비어있으면 1을 리턴하면 정답이 나온다.

 

 

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

using namespace std;

int solution(string s) {
    int answer = -1;

    // base case
    if (s.size() == 1) {
        return 0;
    }
    
    stack<char> st;
    
    for (char c : s) {
        if (st.empty()) {
            st.push(c);
        }
        else {
            if (st.top() == c) {
                st.pop();
            }
            else {
                st.push(c);
            }
        }
    }
    
    if (st.empty()) {
        answer = 1;
    }
    else {
        answer = 0;
    }

    return answer;
}