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

문제 링크

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

내 풀이

처음 시도한 방법
string 의 한글자씩 반복문 돌려가면서 앞글자와 같은 글자가 있으면 그 부분을 제거 ( substr로 해당 부분 제외하고 앞과 뒤를 이어붙혀 string에 다시 넣기 or string::erase활용해서 해당 부분 제거하기 ) 기능은 제대로였지만 이렇게 할 경우 시간복잡도가 어마어마해서 효율성 테스트에서 탈락한다.
힌트를 보고 stack을 사용하게 되었다.string의 한 글자씩 반복문을 돌리면서 stack의 사이즈가 0이상이고 stack의 top에 같은 글자가 있으면 pop, 사이즈가 0이거나 다른 글자면 해당 글자를 push한다. 결국 다 맞아떨어져서 stack이 empty()면 1을 반환, 아니면 0을 반환한다.

내 코드

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

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

다른 사람의 풀이

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

using namespace std;



int solution(string s)
{
    stack<char> c;
    int answer = 0;
    for(int i=0; i<s.size(); i++){
        if(c.size()==0){
            c.push(s[i]);
            continue;
        }
        if(c.top() == s[i])
        {
            c.pop();
        }
        else{
            c.push(s[i]);   
        }
    }
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    if(c.empty())
        answer = 1;
    else{
        answer = 0;
    }

    return answer;
}

다른 사람의 풀이 해석

스택을 사용한 풀이이다.