[Baekjoon(백준)][4949번] 균형잡힌 세상(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "균형잡힌 세상" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 문자열에 있는 괄호들이 올바르게 짝지어져 있는지 확인하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

4949번: 균형잡힌 세상

문제 개요

"균형잡힌 세상" 문제는 주어진 문자열에 있는 괄호들이 올바르게 짝지어져 있는지 확인하는 문제입니다. 괄호는 소괄호("()")와 대괄호("[]") 두 종류가 있으며, 이들이 균형을 이루어야 합니다.

해결 방법

스택을 사용하여 각 괄호의 짝을 확인합니다. 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 상단 요소와 짝이 맞는지 확인합니다. 모든 문자열을 검사한 후 스택이 비어있으면 균형잡힌 문자열로 간주합니다.

코드 구현

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while (true) {
        string str = "";
        getline(cin, str); // 한 줄씩 입력 받기
        if (str == ".") break; // 종료 조건

        bool isPrinted = false;
        stack<char> s;
        for (int i = 0; i < str.size(); i++) {
            // 여는 괄호인 경우 스택에 넣기
            if (str[i] == '[' || str[i] == '(') s.push(str[i]);
            else {
                // 닫는 괄호인 경우 스택의 상단 요소와 짝이 맞는지 확인
                if ((str[i] == ']' || str[i] == ')') && s.size() <= 0) {
                    isPrinted = true;
                    cout << "no" << "\n";
                    break;
                }
                if (s.size() <= 0) continue;
                if (str[i] == ']') {
                    char c = s.top();
                    if (c != '[') {
                        isPrinted = true;
                        cout << "no" << "\n";
                        break;
                    }
                    else {
                        s.pop();
                    }
                }
                else if (str[i] == ')') {
                    char c = s.top();
                    if (c != '(') {
                        isPrinted = true;
                        cout << "no" << "\n";
                        break;
                    }
                    else {
                        s.pop();
                    }
                }
            }
        }
        if (isPrinted) continue;
        if(s.size() <= 0)cout << "yes" << "\n";
        else cout << "no" << "\n";
    }
}

코드 설명

위 코드는 주어진 문자열을 한 줄씩 받아와서 처리합니다. 여는 괄호는 스택에 넣고, 닫는 괄호는 스택의 상단 요소와 짝이 맞는지 확인합니다. 스택이 비어있거나 괄호의 짝이 맞지 않는 경우 "no"를 출력합니다. 모든 문자열을 처리한 후 스택이 비어있으면 "yes"를 출력합니다.

결론

"균형잡힌 세상" 문제는 스택을 활용하여 해결할 수 있습니다. 스택을 사용하여 괄호의 짝을 관리함으로써 균형잡힌 문자열을 판별할 수 있습니다.