[PS] 짝지어 제거하기

문제

해결 - 1

처음에는 일단 브루트포스로 순회하면서 연속된 문자가 잇으면 두 문자를 제외하고 새로운 문자열을 만들어서 순회하는 코드를 짰는데, 당연히 효율성 쪽에서 시간 초과가 발생했다.

고민을 좀 더 해보다가, baab 케이스를 보고 마치 괄호 쌍 찾는 문제 처럼 stack을 사용해서 stack의 top에 잇는 원소와 같은 문자가 오면 pop해버리는 구현법을 선택했다. 이렇게 하면 한번의 순회에 모두 처리 가능하다.

소스코드 - 1

// Authored by : prid1306

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

int solution(string s)
{
    stack<char> st;
    
   for(int i = 0; i < s.length(); ++i)
   {
       if(st.size() == 0)
       {
           st.push(s[i]);
           continue;
       }
       else
       {
           if(st.top() == s[i]) st.pop();
           else st.push(s[i]);
       }
   }

    return st.size() == 0;
}

해결 - 2

하지만 이 문제는 #include로 stack이 기본적으로 포함되어있지 않다.
이게 힌트를 주기 싫어서 뺀건지 아니면 이걸 제외하고 구현하라는 의도로 뺀건진 모르겠지만.

다른 사람들의 소스코드 풀이를 보고 있었는데 이번에도 신기한 풀이 하나를 봐서 기록해두려고 한다.

소스코드 - 2

#include <string>
using namespace std;

int solution(string s) {
    int i = 0;
    for (const char ch : s) {
        if (i > 0 && s[i - 1] == ch)
            i--;  
        else {
            s[i] = ch;
            i++;
        }
    }
    return !i;
}

이건 stack을 for문을 사용해서 구현한건데, s[i-1]번째(스택의 최상단)에 있는 문자와 ch(이번에 순회할 때 사용하는 문자) 가 같으면 pop(i--)을 수행하고 아니라면 s[i] = ch로 문자를 push하고 i++를 해서 다음 여유칸을 준비하는 코드다.

손으로 흐름을 따라가보면 다음과 같다.

이런 능력이 정말 부럽다.