짝지어 제거하기 C++

문제 설명

 

입출력 예

s                                                                                                                                                   result

baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

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

int solution(string s)
{
    int answer = 0;

    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;

    return answer;
}

 

=> 효율성과 정확성을 위해 stack을 사용하면 간단한 문제였습니다. 
*저는 pair를 사용하면서 비교를 하다 보니 효율성에서도 정확성에서도 틀리고 말았습니다. (그래도 replace 함수 공부는 하게 되었습니다.)

=> 질문글들을 보면 stack에 쌓으며 가장 위에 있는 값과 현재 순환하면 바라보고 있는 s [i]의 값이 같을 경우 pop을 해주어 제거할 수 있는 것을 알았습니다. 

=> 아래에는 제가 풀었던 마구잡이 코드도 올려두겠습니다. 

 

int solution4(string s)
{
    int answer=1 ;
    int length = s.size();
    bool check = true;
    pair<char, int> Former,Latter; //문자, index
    char first,second;
    while(check)
    {
        check = false;
        Former.first = NULL;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i] == ' ' )continue;
            if(Former.first) //첫번째 문자가 있는 경우
            {
                Latter.first = s[i];
                Latter.second = i;
                if(Former.first == Latter.first) // 변환가능한 경우
                {
                    s.replace(Former.second, 2, " ");
                    check = true;
                    length -= 2;
                    Former.first = NULL;
                }
                else
                {
                    Former.first = s[i];
                    Former.second = i;
                }
            }
            else//first 빈경우
            {
                Former.first = s[i];
                Former.second = i;
            }
        }
    }
    for(int i=0; i<s.size(); i++)
    {
        if(s[i] != ' ')answer =0;
    }
    return answer;
}
int main()
{
    
    string s("baabaa");
    solution4(s);
    
    return 0;
}