백준 4949번 [균형잡힌 세상](C++)-yes6686- 티스토리

백준 문제 풀이: 4949 [균형잡힌 세상]

---

문제 링크: https://www.acmicpc.net/problem/4949

문제 설명:

주어진 문자열이 균형잡힌 괄호 문자열인지 판단하는 문제입니다. 균형잡힌 문자열은 다음 조건을 만족해야 합니다:

• 모든 여는 괄호 '(' 또는 '['가 적절한 닫는 괄호 ')' 또는 ']'와 매칭되어야 한다.
• 괄호가 중첩되는 경우, 올바른 순서로 닫혀야 한다.

문자열의 끝은 항상 마침표('.')로 표시되며, 입력이 '.' 하나만 있을 경우 프로그램을 종료합니다.

---

문제 해결 코드

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

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

    while (1) {
        string s;
        stack<char> a;
        int check = 1;
        getline(cin, s);
        if (s == ".") {
            break;
        } else {
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '(' || s[i] == '[') {
                    a.push(s[i]);
                } else if (s[i] == ')') {
                    if (a.empty()) {
                        check = 0;
                        break;
                    } else if (a.top() == '(') {
                        a.pop();
                    } else if (a.top() == '[') {
                        check = 0;
                        break;
                    }
                } else if (s[i] == ']') {
                    if (a.empty()) {
                        check = 0;
                        break;
                    } else if (a.top() == '[') {
                        a.pop();
                    } else if (a.top() == '(') {
                        check = 0;
                        break;
                    }
                }
            }
            if (a.empty() && check) {
                cout << "yes" << '\n';
            } else {
                cout << "no" << '\n';
            }
        }
    }
}

---

코드 설명

• 핵심 알고리즘: 스택을 이용하여 괄호의 여닫힘 상태를 추적
• 구현 세부사항:
  • 문자열을 한 글자씩 확인하며, 여는 괄호는 스택에 추가
  • 닫는 괄호는 스택의 최상단과 비교하여 매칭 여부 확인
  • 스택이 비어있는 상태에서 닫는 괄호가 나오거나 매칭이 불가능할 경우 문자열은 균형잡히지 않은 것으로 판정
• 시간 복잡도: O(n)
  • 문자열의 길이 n에 대해 한 번의 순회로 처리 가능

---

결과

주어진 문자열에 대해 균형잡힌 괄호 문자열인지 여부를 출력합니다. 균형잡힌 경우 yes, 그렇지 않은 경우 no를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!