<Programmers> Lv2. String, Stack_짝지어 제거하기 c++

Solution 1

• 탐색하다가 2개가 겹쳐서 나오는 부분이 있으면 해당 부분을 '_'으로 만들어주고 다시 처음부터 순회하는 방법을 사용했다
• 문자열의 길이는 최대 1,000,000이므로 O(N^2)의 시간 복잡도를 가지므로 최대 1,000,000 X 1,000,000 의 시간 복잡도를 가지게 되어 효율성에서 틀렸다

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

int solution(string s) {
    bool flag=true;
    
    while (flag) {
        flag=false;
        
        for (int i=1; i<s.length(); i++) {
            
            int prev=i-1;
            int cur=i;
            
            
            if (s[prev]=='_') continue;
            if (s[cur]=='_') 
                while (cur<s.length() && s[cur]=='_') cur++;
            
            if (s[prev]==s[cur]) {
                s[prev]=s[cur]='_';
                flag=true;
                break;
            }
        }
    }

    for (int i=0; i<s.length(); i++) 
        if (s[i]!='_') return 0;

    return 1;
}

Solution 2

• Stack을 사용하여 글자를 하나씩 넣어보며 top에 있는 글자와 현재 넣으려는 글자가 같으면 pop을 하고 아니면 하나씩 넣으며 확인한다
• O(N)의 시간 복잡도를 가짐

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

int solution(string s) {
    stack<char>str;
    
    for (auto i: s) {
        if (str.empty() || str.top()!=s[i])
            str.push(s[i]);
        else if (str.top()==s[i]) str.pop();
    }
    if (str.empty()) return 1;
    else return 0;  
}