[알고리즘] 짝지어 제거하기

포인트 

1. 스택을 사용할 수 있는가?
정말 신기하게도 문자열을 다루는 것들에서는 Stack 을 많이 쓴다. 

c++/cpp

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

using namespace std;

int solution(string s) {
    int answer = 0;
    stack<char> stack;
    for (int i = 0; i < s.size(); i++) {
        // 1. 스택이 비어 있거나 이전에 스택 top 의 값이 현재 s[i] 와 다르다면 push
        if (stack.empty() || stack.top() != s[i]) {
            stack.push(s[i]);
        } else { // 2. 스택 top 의 값이 현재 s[i]와 같다면 top 에 있는 값을 pop
            stack.pop();
        }
    } // 스택이 비어있다면 문자열을 모두 제거할 수 있고 없다면 실패
    if (stack.empty()) return 1;
    else return answer;
}

python

def solution(s):
    answer = 0
    stack=[]
    
    for ele in s:
        if(len(stack)==0):
            stack.append(ele)
            continue
            
        if(ele==stack[-1]):
            stack.pop()
        else:
            stack.append(ele)
        
    return 1 if len(stack)==0 else 0