[algorithm] 백준 4949번 균형잡힌 세상

 

문제 설명 & 접근 방식

" ( " 는 " ) " 랑만 " [ " 는 " ] " 랑만 맞춰져야하고 한 문장이 완벽히 다 괄호 쌍들이 맞아야 균형잡힌 문자열인 것이다

닫는 괄호가 나왔을 때 짝을 맞추어 소거해가는 방식으로 풀어야된다고 봤으므로 스택을 사용해야한다고 생각했다

 

접근 방식으로는

1. 여는 괄호가 나오면 우선 스택에 push한다

2. 닫는 괄호가 나온 경우

  2-1 스택이 비어있다면 탈락

  2-2 스택의 top이 짝이 안맞으면 탈락

  2-3 스택의 top이 짝이 맞으면 pop

3. 1~2 과정이 끝났는데 스택에 괄호가 남아있으면 탈락 없으면 통과

 

이 규칙으로 구현해주면 된다

 

코드

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

int main() {
    string s;
    vector<string> vec;
    while(1)
        {
            vec.clear();
            getline(cin,s);
            stack<int> st; // 스택 초기화함수 없어서 함수 내에서 선언
            if(s == ".") break;
            else
            {
                for(char c : s)
                    {
                        if(c == '(' || c == '[') st.push(c);
                        
                        if(c == ')')
                        {
                            if(st.size() == 0)
                            {
                                vec.push_back("no");
                                break;
                            }
                            else if(st.top() != '(')
                            {
                                vec.push_back("no");
                                break;
                            }
                            else st.pop();
                        }
                        if(c == ']')
                        {
                            if(st.size() == 0)
                            {
                                vec.push_back("no");
                                break;
                            }
                            else if(st.top() != '[')
                            {
                                vec.push_back("no");
                                break;
                            }
                            else st.pop();
                        }
                    }
                if(vec.size() == 0)
                {
                    if(st.size() == 0) cout << "yes" << "\n";
                    else cout << "no" << "\n";
                }
                else cout << "no" << "\n";
            }
        }
   
    return 0;
}

 

오류

처음엔 마지막 yes, no 판정하는 부분에서

if(st.size() == 0) cout << "yes" << "\n";

 

이 부분 없이 했었는데 " ((. " 이라는 반례가 있어 틀렸었다

즉 닫힌 괄호가 한 번도 나오지 않은 경우에도 yes로 판정됐던 것이다

 

그리고 닫는 괄호 나온 경우 탈락 조건에 걸리면 "no"를 vector에 따로 넣어서 판정했었는데

이는 비효율적이고 boolean 변수를 활용해서 푸는 것이 더 깔끔한 것같다