#9012: 괄호
문제:
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력:
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
풀이:
- 처음 이 문제를 풀 때 그냥 왼쪽 오른쪽 괄호 개수를 센 뒤 같으면 되는게 아닌가 싶었지만 이렇게 풀면 닫기 괄호가 먼저 오게 되도 개수는 같지만 VPS가 안되기 때문에 스택을 이용하여 문제를 풀게 되었다.
- 우선, 메모리 사용량을 줄이기 위해 스택을 이용할 때 0은 여는 괄호 1은 닫는 괄호로 지정하여 boolean을 사용하는 스택을 만들었다.
- 문제를 풀 때 결국 우리의 목표는 괄호들의 짝이 맞는지 확인하면 되고 제일 안쪽의 VPS 괄호쌍은 바로 옆에 붙어 있을 것이기 때문에 ‘)’ 문자를 접하였을 때 스택 제일 위에 ‘(’가 있는지 확인 한뒤 있으면 같이 pop해주어 마지막에 스택에 아무것도 남지 않으면 짝이 모두 맞다는 뜻이므로 YES를 출력하면 되고 그 외에 아닐 경우는 NO를 출력해주면 된다.
⚠️ stack.top()을 이용할 때 stack이 빈 상태면 이상한 결과가 나온다. Geekforgeeks 사이트의 글(https://www.geeksforgeeks.org/stack-top-c-stl/)에 의하면 “If the stack container is empty, it causes undefined behavior”라고 한다. 작성자 같은 경우는 프로그램이 작동을 중지했다. 스택이 비어 접근 할 수 있는 데이터가 없어서 그런 것 같다. 따라서, 스택이 비었나 같이 확인해주어야 된다.
코드:
#include <iostream>
#include <stack>
#define LEFT 0
#define RIGHT 1
using namespace std;
int main(){
int n;
cin >> n;
cin.ignore(); //getline() 빈 줄 불러오기 방지
for(int i = 0; i < n; i++){
string str = "";
getline(cin, str);
stack<bool> stack;
for(int j = 0; j < str.size(); j++){
//왼쪽 괄호 일 때 스택에 넣기
if(str[j] == '(') stack.push(LEFT);
//오른쪽 괄호 일 때
else{
/*스택이 비었나 같이 확인안하면 undefined behavior 발생*/
//스택이 안비었고 왼쪽 괄호가 존재하면 제일 위에 있는 왼쪽괄호를 pop
if(!stack.empty() && stack.top()==LEFT) stack.pop();
//스택이 비었거나 제일 위에 있는 괄호가 왼쪽 괄호가 아니면 어짜피 VPS가 아니므로 break
else{
stack.push(RIGHT); //비어있는 스택인 경우에는 아래에서 NO를 받기 위해 RIGHT을 스택에 push
break;
}
}
}
if(stack.empty()) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
Leave a comment