수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 4949 균형잡힌 세상 본문

알고리즘/C++

[C++] BAEKJOON 4949 균형잡힌 세상

ssung.k 2019. 10. 5. 01:56

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

 

4949번: 균형잡힌 세상

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다. 모든 왼쪽 대괄호("[")는 오른쪽 대

www.acmicpc.net

일반적으로 스택를 써서 올바른 괄호를 체크하는 문제에서 괄호의 종류를 늘려 약간의 응용이 필요한 문제였습니다.

입력

string s;
getline(cin, s);

입력은 띄어쓰기가 포함된 문장이기 때문에 getline 을 이용해서 받았습니다.

올바른 괄호 확인

하나의 스택를 사용하여 두 괄호의 유효성을 확인해줄 수 있습니다. 아래와 같은 알고리즘으로 이를 확인합니다.

  • ([ 가 들어올 경우에는 스택에 담아줍니다.

  • ) 가 들어왔을 경우에는 아래 두 가지 조건을 확인합니다.

    • 스택이 비어있다면 false
    • 스택의 마지막 값이 ( 가 아니라면 false

    두 가지 조건에 문제가 없다면, 마지막은 ( 라는 의미입니다. () 짝이 맞았으므로 스택에서 ( 를 pop 하여 줍니다.

  • ] 가 들어왔을 경우에는 아래 두 가지 조건을 확인합니다.

    • 스택이 비어있다면 false
    • 스택의 마지막 값이 [ 가 아니라면 false

    두 가지 조건에 문제가 없다면, 마지막은 [ 라는 의미입니다. [] 짝이 맞았으므로 스택에서 [ 를 pop 하여 줍니다.

  • 마지막으로 스택이 차있다면 false, 그렇지 않으면 true

 

#include <iostream>
#include <stack>

using namespace std;

int main(){
    while (1){
        stack <char> st;
        string s;
        getline(cin, s);
        
        if (s=="."){
            break;
        }
        int flag = 0;
        for (int i=0;i<s.size();i++){
            char c = s[i];
            if (c == '(' || c=='['){
                st.push(c);
            }
            else if (c == ')'){
                if (st.empty() || st.top()!='('){
                    flag = 1;
                    break;
                }
                st.pop();
            }
            else if (c == ']'){
                if (st.empty() || st.top()!='['){
                    flag = 1;
                    break;
                }
                st.pop();
            }
        }
        
        if (flag || !st.empty()) cout << "no\n";
        else cout << "yes\n";
        
    }
    
    return 0;
    
}

 

Comments