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

짝지어 제거하기

요즘 구현문제만 풀다보니 이 문제를 풀 때 자료구조가 떠오르지않았다.

그래서 처음엔 구현으로 풀었는데 시간초과가 났다. 알고보니 stack을 떠올리면 금방 풀 수 있는 문제였다.

[stack을 사용한 코드]

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

using namespace std;

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

[시간초과나는 코드]

#include <iostream>
#include <string>

using namespace std;

int solution(string s) {
    int answer = 0;
    pair<int, int> k = {0,0};
    
    while(true) {     
        bool flag = false;
        
        if (s.empty()) {
            answer = 1;
            break;
        }
        
        for(int i=1; i<s.size(); i++) {
            if (s[i-1] == s[i]) {
                k = {i-1, i};
                flag = true;
                break;
            }
        }
        if (flag) {
            s.erase(s.begin() + k.second);
            s.erase(s.begin() + k.first);
        }

        if (!flag) break;
    }

    return answer;
}