[스택] 균형잡힌 세상(4949)(C++)

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

1. 문제 개요

 

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

 

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

 

 

2. 입출력

 

 

3. 문제 풀이

 

스택과 vector의 find 함수 두 가지 방법을 통해 해결했다.

 

스택을 사용하는 방법은 스택의 후입선출이라는 특성을 사용한다.

우선, 시작 괄호 --> '(' , '[' 일때 문자를 스택에 푸쉬하고 닫는 괄호일때 --> ')' , ']' 스택의 탑이 짝이 되는 괄호일때 스택을 팝하면서 문자열의 짝이 맞는지 확인하는 것이다. 

문자열이 종료될때까지 위의 과정을 반복하다가 짝이 맞지 않는 경우가 나온다면 정답은 "no"가 되며, 마지막 문자까지 검사가 종료된 후 슽택이 비어있으면 정답은 "yes"가 된다.

 

두번째로 vector의 find 함수를 사용해서 해결하는 방법은, 문자열을 입력받은 후 '(', ')', ']', '[' 네 가지 문자에 대해서만 새로운 문자에 더해준다. 따라서 "([ (([( [ ] ) ( ) (( ))] )) ])."와 같은 문자열을 넣게 되면 새로운 문자열은 ([(([([])()(())]))])가 된다.

그 다음 새로운 문자열에 대해 "[]", "()" 이렇게 두 가지의 문자열을 포함하고있다면 이를 지워준다. 문자열에 변화가 없을 때까지 이를 반복해주고, 균형잡힌 문자열일 경우 문자열의 길이가 0이 되고, 그렇지 않은 문자열의 경우 문자열의 길이가 1 이상이 된다.

 

 

4. 전체 코드

 

vector의 find 함수를 사용하는 경우

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void) {
    vector<char> v;
    vector<string> checkV = {"()","[]"};
    
    string str, newStr;
    getline(cin, str);
    
    while(str != ".") {
        newStr = "";
        for(int i=0;i<str.length();i++)
            if(str[i]=='('||str[i]==')'||str[i]=='['||str[i]==']')
                newStr += str[i];
        
        cout << newStr << endl;
        
        while(1) {
            string prestr = newStr;
            for(int j=0;j<checkV.size();j++) {
                int idx = newStr.find(checkV[j]);
                if(idx==string::npos) continue;
                newStr.replace(idx, 2, "");
            }
            if(prestr==newStr) break; // 변화가 없다면 정지
        }
        
        if(newStr.length()==0) printf("yes\n");
        else printf("no\n");
        getline(cin, str);
    }
}

 

스택을 사용하는 경우

#include <iostream>
#include <stack>
#include <map>

using namespace std;

int main(void) {
    string str;
    map<char, char> mp;
    mp.insert({']','['});
    mp.insert({')','('});
    
    while(1) {
        stack<char> st;
        string ans = "yes\n";
        getline(cin, str);
        if(str==".") break;
        for(int i=0;i<str.length();i++) {
            if(str[i]=='['||str[i]=='(') {
                st.push(str[i]);
            } else if(str[i]==']'||str[i]==')') {
                if(!st.empty()&&st.top()==mp[str[i]])  st.pop();
                else ans = "no\n";
            }
        }
        if(!st.empty()) cout << "no" << "\n";
        else cout << ans;
    }
}