백준 9012번 [괄호](C++)-yes6686- 티스토리

백준 문제 풀이: 9012 [괄호]

---

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

문제 설명:

주어진 문자열이 올바른 괄호 문자열(Valid Parenthesis String, VPS)인지 판단하는 문제입니다. 문자열은 '('와 ')'로만 구성되며, 다음 조건을 만족해야 올바른 괄호 문자열로 간주됩니다:

• 왼쪽 괄호 '('의 개수와 오른쪽 괄호 ')'의 개수가 같아야 합니다.
• 왼쪽 괄호가 오른쪽 괄호보다 먼저 등장해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    string s;
    int cnt = 0;

    while (T--) {
        cin >> s;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                cnt++;
            } else {
                if (cnt == 0) {
                    cnt++;
                    break;
                } else {
                    cnt--;
                }
            }
        }

        if (cnt == 0) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
        cnt = 0;
    }
}

---

코드 설명

• 핵심 알고리즘: 카운터를 이용하여 괄호 문자열의 균형을 확인
• 구현 세부사항:
  • 문자열을 한 문자씩 읽으면서, '('가 등장하면 카운터를 증가
  • ')'가 등장했을 때, 카운터가 0이면 이미 균형이 깨진 것으로 판단
  • 문자열을 끝까지 확인한 후, 카운터가 0이면 "YES", 그렇지 않으면 "NO" 출력
• 시간 복잡도: O(T * n)
  • 각 테스트 케이스에 대해 문자열의 길이만큼 반복

---

결과

문자열을 스캔하여 괄호의 균형을 확인하고, 올바른 괄호 문자열 여부를 출력합니다.

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