[프로그래머스/C++] 올바른 괄호

(8/12 - O)

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

프로그래머스

 

구현

스택을 두 개 이용했다.

1. st에 있는 문자들을 st2에 옮겨 담는데, 옮겨 담을 때마다 두 개의 스택의 top끼리 비교해서, 그 둘이 완성된 괄호 형태라면 두 개의 스택에서 모두 pop을 수행하고, 미완성된 괄호 형태라면 그대로 옮겨 담고 st에서만 pop을 수행한다.

2. 1을 반복하여 수행하다가 st가 empty가 되면 멈춘다.

3. st2가 empty라면 괄호들이 모두 완성된 거고 empty가 아니라면 괄호가 미완성된 형태의 문자열이다.

 

 

실수

"()"일 때만 완성된 괄호이고, ")("일 때는 완성된 괄호가 아니다. 단순히 st와 st2의 top()끼리 다르다고 해서 완성된 괄호라고 판단하면 안 된다!

 

 

코드

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

using namespace std;

bool solution(string s)
{
    bool answer = true;

    stack<char> st;
    for (const auto& c : s) {
        st.push(c);
    }

    stack<char> st2;
    while(!st.empty()){
        if (st2.empty()) {
            st2.push(st.top());
        }
        else if (st.top() == '(' && st2.top() == ')') {
            st2.pop();
        }
        else {
            st2.push(st.top());
        }
        st.pop();
    }

    answer = st2.empty();
    return answer;
}