[Programmers/Level2] 프로그래머스 - 짝지어 제거하기 [C++풀이]

 

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

프로그래머스

 

정말정말 오랜만에 푸는 알고리즘 문제...

연속으로 같은 문자가 나오면 제거해주고 앞 뒤를 이어 붙여서 다시 체크한다.

ABBAAA 면 true,

ABBBAA 면 false가 나온다.

문자열이 홀수개라면 구성과 관계없이 false.

 

보자마자 Stack을 이용해야 한다는 것을 알았지만 너무 오랜만이라 구현이 오래걸렸다 ㅜ

 

풀이

#include <bits/stdc++.h>
using namespace std;

int solution(string s)
{
    bool answer = false;
    stack <char> stk;
    
    // 전체 문자열의 길이가 짝수일 때만 비교해준다.
    if(s.length() % 2 == 0){
        for(int i = 0; i < s.length(); i++){
        	// 스택 사이즈가 1 이상일 때부터 비교할 것임
            if(stk.size() > 0){
                // 두 개가 같다면 지워주기
                if(stk.top() == s[i]){
                    stk.pop();
                }
                // 같지 않다면 그냥 넣어주기
                else{
                    stk.push(s[i]);
                }
            }
            // 스택에 아무것도 없다면 비교할 게 없으니 그냥 push
            else{
                stk.push(s[i]);
            }
        }
        // 최종적으로 길이가 0이 되면 성공!
        if(stk.size() == 0){
            answer = true;
        }
    }
    
    return answer;
}