BOJ 9012. 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
1. 문제 이해
먼저, 문제의 정확한 이해를 위해 예시로 주어진 내용을 살펴본다.
- ex1. ( ( ) ) ( ) ---> VPS
- ex2. ( ( ( ) ) ) ---> VPS
- ex3. ( ( ) ( ---> VPS x
- ex4. ( ( ) ) ( ) ) ) ---> VPS x
- ex5. ( ( ) ---> VPS x
이는 쌍이 가장 가까운 여는괄호와 닫는괄호를 찾는 문제이다. 여는 괄호는 닫는 괄호가 있을때 의미가 있다. 그러므로 닫는 괄호에 대한 여는 괄호를 찾아야 한다. 닫는 괄호가 나왔을때 그에 대한 여는 괄호를 앞에서 쭉 찾아가면서 가장 가까운 곳에 쌍을 이루지 않았던 여는 괄호가 있다면 짝을 맞추어 주는 방식으로 해결하는 것을 생각해볼 수 있다. 이 조건을 요약하면 다음과 같다.
- 조건
1) 닫는 괄호의 앞에 있는 여는 괄호만 가능하다.
2) 다른 닫는 괄호과 짝이 아닌 것이어야 한다.
3) 가장 가까운 여는 괄호가 짝이 된다.
( ( ) ) ( )
1 2 3 4 5 6
이 예시에서는 3번에서 닫는 괄호가 나왔으므로, 앞의 2, 1번을 순차적으로 탐색한다. 우선 앞에 있고, 다른 닫는 괄호와 짝이 아니기 때문에 1), 2)번 조건은 모두 만족한다. 그 중에서 가장 가까운 2번 괄호와 짝이 된다. --> 그 다음 4번이 나오고 앞에 여는 괄호인 2, 1번을 탐색한다. 2, 1번은 모두 앞에 있고 여는 괄호이지만, 2번은 이미 3번과 짝이 되었으므로 1번과 짝이 된다. --> 마지막으로 6번은 닫는 괄호이므로 앞에 있고, 다른 닫는 괄호와 짝이 아니면서, 가장 가까운 5번과 짝이 된다.
이런식으로 실행되면 각 닫는 괄호마다 앞에 있는 여는 괄호를 모두 조사하게 되므로 O(N^2)의 시간복잡도를 가진다.
2. 문제 풀이
스택을 활용한 풀이
이 문제를 풀기 위해 스택 자료구조를 활용할 수 있다. '가장 가까운' 여는 괄호를 찾는다는 부분에서 힌트를 얻을 수 있다. 이는 '가장 위에 있는' 값만 볼 수 있는 스택 자료구조를 활용하기에 적합하다. 그렇다면 닫는 괄호를 만날때까지는 스택에 여는 괄호를 모두 Push 해가면서 닫는 괄호를 만나게 되면 Pop하여 짝은 맞춰주면 된다.
스택에 들어가는 것은 정답 후보인 여는 괄호만 해당되는데, 이는 닫는 괄호를 만나기 전까지 모두 넣으므로 1)번 조건을 만족하며, 2)번 조건을 만족하는 것만 스택에 계속 넣을 것이다. 마지막으로, 3)번 조건은 스택의 특성으로 '가장 위에 있는 값' 이 '가장 가까운 값' 이 되므로 Pop을 하면 된다. 첫번째 예시를 그림으로 나타내면 아래와 같다.
( ( ) ) ( )
1 2 3 4 5 6
닫는 괄호가 나올때마다 스택에서 Pop연산을 하고, 마지막에 스택이 비어있다면 VPS이며, 그렇지 않다면 VPS가 아니다.
( ( )
1 2 3 같은 경우에는 마지막에 스택에 1번 괄호가 남아있어서 VPS가 아니다.
( ) )
1 2 3 같은 경우에는 마지막에 스택에 남아있는 값이 없어서 짝을 맞추지 못하므로 VPS가 아니다.
#include <iostream>
#include <string>
using namespace std;
string VPS(string s) {
int top = 0;
for (int i=0; i<s.size(); i++) {
if (s[i] == '(') top++; // 여는 괄호는 스택에 넣음
else top--; // 닫는 괄호이면 pop
if (top < 0) return "NO"; // 닫는 괄호가 더 많은 경우
}
if (top == 0) return "YES"; // 스택이 비었으면 VPS
else return "NO"; // 스택이 비어있지 않다면 VPS가 아님
}
int main() {
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
cout << VPS(s) << '\n';
}
return 0;
}실제로 구현할 때는 스택을 직접 구현하지 않더라도 top값의 결과만으로 해결이 가능하다. 최종적으로 top값이 0이 아니라면 무조건 짝이 맞지 않는 경우이기 때문이다. 단, 닫는 경우가 더 많은 경우에는 (스택에 값이 없는 경우와 같다.) 바로 리턴 해주어야 한다.
( ) ) (
1 2 3 4
이런 경우에는 3번 에서 top값은 -1이 되는데, 만일 종료되지 않는 다면 4번에서 결과적으로 top값이 0이 될 것이므로 결과가 YES로 잘못 출력될 수 있다.
