[백준 알고리즘] 백준 9012번: 괄호 / 파이썬 Python3 (스택)
🔔 문제
출처 : https://www.acmicpc.net/problem/9012
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 124445 | 56604 | 40959 | 44.410% |
괄호 문자열(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
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
예제 출력 1
NO
NO
YES
NO
YES
NO
예제 입력 2
3
((
))
())(()
예제 출력 2
NO
NO
NO
출처
ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2012 G번
알고리즘 분류
🔐 해결 (소스 코드)
T = int(input())
for _ in range(T):
stack = []
str = input()
# 괄호 판별을 위한 반복문
for c in str:
if c == '(':
stack.append(c)
elif c == ')':
# stack에 뭐라도 있는 경우
if stack:
stack.pop()
# stack에 아무것도 없는 경우
else:
print("NO")
break
# break문이 걸리지 않을 경우를 대비해서 for-else문을 이용해서 한번 더 체크하면서, 최종 결과값인 YES와 NO를 판별
# for-else문 참고 출처 : https://harryp.tistory.com/317
else:
if len(stack) == 0:
print("YES")
else:
print("NO")
📝 후기
아무 생각없이 샤워를 하다가 “이 문제를 풀 수 있을 것 같다”는 생각이 들어 즉흥적으로 풀게 되었다.
이번 문제를 풀면서 배울 수 있었던 것은 for-else 문이었다.
(참고한 사이트 링크 : https://harryp.tistory.com/317)스택 문제니까 ‘스택’스럽게 접근했는데, 아는대로 해보니까 출력 결과값이 원하는대로 출력이 되지 않았다.
그래서, 내가 해놓은 것에서 수월하게 적용할 수 있는 해결 방법을 찾다보니 ‘for-else문’에 대해서 보게 되었고, 그대로 풀이에 적용해보면 좋겠다는 생각이 들어서 적용해봤더니 코드가 잘 동작하였다.
이 문제와는 상관없이 여담으로 요즘, 정보처리기사 실기 공부를 우선 순위로 해서 병행하고 있는데, 공부하면서도 내가 여러가지 기술을 다뤘다보니 (기초적인 부분이라도) 알고 있다가도 잠시동안 백지 상태가 될 때가 있다. 그런 점이 곧, 내가 부족하다는 증거라고 생각한다. 그걸 요즘 정말 많이 느끼고 있다. 😥
나의 그 부족함을 빨리 채우고 싶다.
Leave a comment