[C++] 백준(BOJ) - 4949 : 균형잡힌 세상

10 Oct 2023 in Develop on C++, Algorithm Last modified at: 2024-08-16

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 4949 : 균형잡힌 세상(링크)

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

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

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

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

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

알고리즘

1. 자료구조
2. 문자열
3. 스택

풀이

• 띄어쓰기를 포함한 string 읽어들이기 => getline
• 매 테스트케이스마다 결과 값을 비교하는 문제는 초기화가 중요!
• Stack 자료구조를 사용할 때는 Stack size를 항상 체크하는 것을 잊지말자

코드

// BOJ - 4949 : 균형잡힌 세상
#include <bits/stdc++.h>
using namespace std;

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

    while (true)
    {
        string str;
        getline(cin, str); // 띄어쓰기를 포함한 string 읽어 들이기

        if (str == ".") break;
        
        stack<char> stk;
        bool flag = true;

        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == '(' || str[i] == '[') stk.push(str[i]);
            if (str[i] == ')')
            {
                if (stk.empty() || stk.top() == '[')
                {
                    flag = false;
                    break;
                }
                else
                {
                    stk.pop();
                }
            }
            if (str[i] == ']')
            {
                if (stk.empty() || stk.top() == '(')
                {
                    flag = false;
                    break;
                }
                else
                {
                    stk.pop();
                }
            }
        }

        if (flag && stk.empty()) cout << "yes" << '\n';
        else cout << "no" << '\n';
    }
    
    return 0;
}

평가

• 짝을 지어, 폭발과 관련된 단어가 문제에서 나오면 스택 자료구조를 연상한다