[C++] 백준 9012 - 괄호(스택 활용)

0. 주어진 문제

괄호 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	35403	14018	10337	38.999%

문제

괄호 문자열(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)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

1. 풀이

1) 스택을 활용해 여는 괄호는 무조건 스택에 집어넣었다.

2) 닫는 괄호가 나오는 경우에 스택의 top과 비교하며 판별을 하였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include<iostream> #include<stack> #include<string> #include<algorithm>   bool wellMatched(const std::string& formula) {     //여는 괄호 문자와 닫는 괄호 문자     const std::string opening("("), closing(")");     //열린 괄호들을 순서대로 담는 스택     std::stack<char> openStack;     for (int i = 0;i < formula.size();i++) {         //여는 괄호인지 닫는 괄호인지 확인한다.         if (opening.find(formula[i]) != -1)             //여는 괄호라면 무조건 스택에 집어넣는다.             openStack.push(formula[i]);         else {             //이 외의 경우 스택 맨 위의 문자와 맞춰보자.             //스택이 비어 있는 경우에는 실패             if (openStack.empty()) return false;             //서로 짝이 맞지 않아도 실패(사실 이 코드는 "({["과 ")}]"의 3개의 괄호를 사용하는 예제에서 가져왔다.)             if (opening.find(openStack.top()) != closing.find(formula[i]))                 return false;             //짝을 맞춘 괄호는 스택에서 뺀다.             openStack.pop();         }     }       //닫히지 않은 괄호가 없어야 성공     return openStack.empty(); }   int main() {     bool is_match;     int n;     std::string Parenthesis;     std::cin >> n;     for (int i = 0; i < n;i++) {         std::cin >> Parenthesis;         is_match = wellMatched(Parenthesis);         if (is_match)             std::cout << "YES\n";         else             std::cout << "NO\n";     }     } Colored by Color Scripter

cs

3. 문제 출처

https://www.acmicpc.net/problem/9012

4. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.634~635.