[Programmers] 짝지어 제거하기

문자열 중 똑같은 단어가 두번 반복되면 제거하고, 이 과정을 반복하는 문제이다.

예를들어 baabaa가 있다면 baabaa -> bbaa -> aa -> 없음
과 같이 문자열이 완전히 지워지면 1을, 안지워진다면 0을 반환하는 문제이다.

문제풀이 전략
처음에는 투포인트를 활용하여 풀려고 했다.

하지만 투포인트를 사용하기 위해서는 만약 문자가 같은 경우 지워진 후 이전 문자를 가리키기 위해 탐색을 해야한다. 이 과정을 하기 위해 이전 위치를 저장하거나 반복문을 통해 탐색하여야 하는데, 시간초과가 걸리게 된다.

따라서 stack을 사용하여 문제를 풀어 보았다.

한 글자 씩 스택에 집어 넣으면서 스택의 top과 현재 가리키고 있는 문자가 같으면 스택을 pop 한 후, 다음 문자를 가리키도록 한다.

반면 문자가 다른 경우 현재 가리키는 문자를 스택에 push 한 후 다음 문자를 가리키도록 한다.

만약 가리키는 문자가 문자열의 끝 이후 일 때 스택이 비어있다면 다 지워졌다는 의미이므로 1을 반환하고, 아니라면 지워지지 않은 것이므로 0을 반환하도록 한다.

코드

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

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

    stack<char> st;

    st.push(s[0]);
    int idx = 1;

    while(1){
        if(!st.empty() && st.top() == s[idx]){
            st.pop();
            idx++;
        }else{
            st.push(s[idx]);
            idx++;
        }

        if(idx >= s.size()){
            if(st.empty()){
                answer = 1;
            }else
                answer = 0;
            break;
        }
    }

    return answer;
}

출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/12973