Algorithm/Algorithms Practice
[BOJ/C++] 괄호(9012번)
Patrick_
2022. 7. 4. 17:00
1. 문제 개요
https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
1-1. 설명
괄호 문자열은 두 개의 괄호 기호인 '('와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(VPS)이라 한다. 한 쌍의 괄호 기호로 된 "()" 문자열은 기본 VPS라 부른다. x가 VPS라고 가정할 때 이것을 하나의 괄호에 넣은 새로운 문자열 "(x)"도 VPS가 된다. 그리고 두 VPS x와 y를 접합 시킨 새로운 문자열 xy도 VPS가 된다. 우리는 입력으로 주어진 괄호 문자열이 VPS인지 아닌지 판단해서 그 결과를 YES와 NO로 나타내야 한다.
1-2. 제한 사항
- T개의 테스트 데이터로 주어짐.
- T는 첫째줄에 입력, 그 외의 괄호 쌍은 두번째줄부터 입력
- 괄호 문자열의 길이는 2이상 50이하
2. 구현
2-1. 풀이
stack을 통해 '('일 땐 push를 통해 저장한 후, ')'가 나오면 pop을 한다. 여기서 ')'가 먼저 나오는 경우를 생각하여 이럴 경우에는 NO가 출력되고, 그 외에 모든 문자를 확인한 후 stack이 비어있으면 YES가 출력되게끔 한다.
2-2. 코드
#include <iostream>
#include <stack>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, flag;
string input;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> input;
flag = 0;
stack<char> parenthesis;
for (char ch : input) {
if (ch == '(') parenthesis.push(ch);
else if (ch == ')') {
if (!parenthesis.empty()) parenthesis.pop();
else {
cout << "NO" << "\n";
flag = 1;
break;
}
}
}
if (flag == 0) {
if (parenthesis.empty()) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
}
}