[문제]
괄호 문자열(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 이하이다.
1
2
3
4
3
((
))
())(()
[출력]
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
1
2
3
NO
NO
NO
[풀이]
stack을 사용하는게 정석이지만! 다른 방법으로도 풀이 가능!
(풀이1) stack 사용
- stack에 아무것도 없으면 괄호 집어넣기
- stack에 괄호가 들어있을 경우 yes / 남아 있는 경우 no
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
for i in range(n):
stack = []
bracket = input()
for b in bracket:
if b == '(':
stack.append(b)
elif b == ')':
if stack:
stack.pop()
else:
print('NO')
break
else:
if not stack:
print('YES')
else:
print('NO')
(stack을 활용한 다른 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
for i in range(n):
stack = []
bracket = input()
for b in bracket:
if b == '(':
stack.append(b)
else:
if stack:
stack.pop(-1)
else:
result = False
break
if result and not stack:
print('YES')
else:
print('NO')
(풀이2) count 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'''
for문 n번 반복
1. 기존 괄호와 비교
2. open과 close의 괄호 수를 누적
3. 수가 같으면 -> YES, 다르면 -> NO
'''
n = int(input())
for i in range(n):
#괄호 string 받기
bracket = input()
r_count, l_count = 0, 0
for b in bracket:
if b == '(':
r_count += 1
else:
l_count += 1
if r_count != l_count:
print('NO')
else:
print('YES')
→ 직관적이고, 굉장히 쉬운 방법이지만 코드의 효율 측면에서는 메모리도 많이 차지하고 속도가 느리다는 단점이 존재 !
→ 괄호의 순서를 고려하지 않기 때문에 count를 누적하는 것이 가능!
([leet]valid-parantheses 문제의 경우 → 괄호의 순서 또한 고려해야 되기 때문에 stack을 사용한 방법만 가능!)