백준 9012번 : 괄호 (C++)

www.acmicpc.net/problem/9012

9012번: 괄호

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

코드

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

풀이

입력된 괄호들을 왼쪽부터 순서대로 검사했을 때 괄호가 올바르지 않은 괄호 문자열임을 알 수 있는 방법은

 

1. 닫아줄 여는 괄호 ' ( ' 가 없는데 닫는 괄호 ' ) ' 가 나왔을 때

2. 모든 괄호들을 검사했는데 닫는 괄호로 닫히지 않은 여는 괄호가 남아있을 때

 

두 가지로 정리할 수 있다.

 

괄호들을 순서대로 검사하면서 여는 괄호 ' ( '가 나왔을 땐 n+1을 해준다. 닫는 괄호 ' ) ' 가 나왔다면 변수 n을 검사해서 n이 0이라면 닫을 여는 괄호가 없는데 닫는 괄호가 나온 것 이다. 따라서 n 값을 -1로 만든 뒤 break 해서 33번 행의 if 문으로 보내주고 else의 NO 출력이 실행된다. 22번 행의 if 문에 걸려서 break 되지 않더라도 모든 괄호 쌍을 검사한 뒤 n의 값을 검사한다. 만약 n이 0이면 닫아줄 여는 괄호가 없는데 닫는 괄호가 나온 적이 없고 닫히지 않은 여는 괄호가 남아있는 것도 아니기 때문에 YES가 출력된다. 그게 아니라면(n이 0이 아니라면) 닫히지 않은 여는 괄호가 있는 것이므로 NO를 출력한다.