문제

투포인터는 정답이 아님

#include <iostream>
#include <string>

using namespace std;

int solution(string s)
{
    int min = 0;
    int l = 0;
    int r = 1;
    
    while(true)
    {
        if(l >= s.size() && r >= s.size()) return 1;
        else if(l < s.size() && r >= s.size()) return 0;
        
        while(l >= 0 && s[l] == '*') l--;
        
        if(l < 0) { 
            l = r; 
            r++; 
            continue; 
        }
        
        while(r < s.size() && s[r] == '*') r++;
        
        if(r >= s.size()) return 0;

        if(s[l] == s[r])
        {
            s[l] = '*';
            s[r] = '*';

            if(l == min)
            {
                l = r+1;
                min = l;
                r += 2;
            }
            else
            {
                l--;
                r++;
            }
        }
        else
        {
            l = r;
            r++;
        }
    }
    
    return 1;
}

이런 코드를 짯음

애초에 100만개의 char문자열이라
2중 for문만 피하자는 생각으로 최대한 O(n)에 맞추기 위해 노력했음

결국 반복횟수는 더하고 빼고 합쳐도 선형시간에서 벗어나지 않으니까
추가적으로 공간 복잡도도 고려해서 100만개의 bool배열을 사용하기보다
문자열을 바꾸면서 최대한 공간복잡도도 아끼고자 했음

테스트케이스는 다 맞췄지만 효율성에서 터져나가는걸 보고
내가 잘못됐다는걸 깨달음

문제점은 하나임
최악의 경우 $O(n^2)$이 된다는거임

min으로 더이상 l을 움직일 수 없는경우 새로 이동을 시키고 있음
l과 r이 문자열 처음에서부터 매칭이 시작되었다고 해보자
예를들어 aabbccddeeff...aabcc이런 문자열이었던거지

거의 끝지점에 이상한 매칭이 안되는 문자가 하나 껴있음
이미 n번의 반복횟수를 가진채로 끝까지 갔는데,
틀린 문자부분만 체킹하는게 아닌 min까지 l이 내려왔다가 다시 매칭이 안된 부분으로 돌아가게 됨

그럼 $O(n^2)$가 되는거지

스택

스택을 활용하는게 가장 좋은 방법임

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

using namespace std;

int solution(string s)
{
    stack<char> st;

    for(char c : s)
    {
        if(!st.empty() && st.top() == c)
        {
            st.pop();
        }
        else
        {
            st.push(c);
        }
    }

    return st.empty() ? 1 : 0;
}

아이디어도 간단함

스택에서 제일 윗 문자와 현재 주어지는 문자를 비교해서 같다면 pop을 통해 선입후출구조에 맞춰
이번에 매칭된 문자보다 먼저 들어왔지만 매칭되지 않은 문자가 위에 올라오게 되고,
비어있거나 매칭되지 않으면 다시 새로운 주어진 문자를 push하고
그게 아니라면 pop을 하면 됨