프로그래머스, 짝지어 제거하기: C++ [CPP] ★★★★

스택을 아는데도

문제를 보면 막상 생각이 안난다.

 

스택의 문제를 생각해보면 스택은 바로 이전의 것과 비교하는 것이 많이 나온다.

이 문제도 마찬가지였다.

https://programmers.co.kr/learn/courses/30/lessons/12973

 

---

 

#맞은 풀이

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

int solution(string s)
{
    int answer = -1;
    
    //문자의 개수가 홀수라면 모두 없앨 수 없음
    if(s.size()%2 == 1) return 0;
    
    stack <char> stk;
    
    for(char x : s){
        if(stk.empty()){
            stk.push(x);
        }else{
            if(stk.top() == x) stk.pop();
            else stk.push(x);
        }
    }
    
    if(stk.empty()){
        answer = 1;
    }else{
        answer = 0;
    }


    return answer;
}

 

분명 쉬웠는데..

Brute Force로 풀자마자 효율성 박살났다.

알면서도.. 처음엔 그렇게 풀었다..ㅎ

짝지어졌다. 그것도 앞뒤로?? 그럼 스택을 생각할만하다.

괄호문제랑 같다.

바로 알아채지 못했을 뿐