백준 9012번 풀이

Stack 실습을 위한 문제입니다. (실버 IV)

문제 내용

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

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

조건

괄호 문자열의 길이는 2 ~ 50자이다.
시간제한: 1초
메모리제한: 128MB

풀이 과정

문제 이해

해당 문제는 단순한 괄호 계산이므로 문제 이해 단계가 필요 없었다.

3
(()) #YES
(((( #NO
()()() #YES

과정 풀이

1. 괄호의 수 T 입력
2. 괄호 문자열 받을 arr 입력
3. 반복을 돌면서 '('를 만나면 stack에 넣기
4. 반복을 돌면서 ')'를 만나면 stack에서 빼기
5. 괄호가 완성되지 않은 경우 NO, 완성됐으면 YES
6. stack 비우고 남은 문자열 반복

구현 1 (초기화)

import sys
input = sys.stdin.readline

T = int(input())
stack = []
arr = []
check = 0 
for i in range(0, T):
    arr += input().split()

• 초기화 부분
• check는 괄호가 ')'로 시작하는 경우를 찾기 위한 변수

구현 2 (괄호 비교)

for i in arr:
    for a in i:
        if a == '(':
            stack.append(a)
        elif a == ')':
            if len(stack) < 1:
                check =- 1
                break
            stack.pop()
            
    if len(stack) > 0 or check == -1:
        print("NO")
        check = 0
    else:
        print("YES")
    stack = []

• 위 과정풀이처럼 각각 '(', ')'에 대하여 stack에 append(), pop()연산을 해준다.
• stack이 비어있는지와 check로 NO, YES처리를 진행

정답

import sys
input = sys.stdin.readline

T = int(input())
stack = []
arr = []
check = 0
for i in range(0, T):
    arr += input().split()

for i in arr:
    for a in i:
        if a == '(':
            stack.append(a)
        elif a == ')':
            if len(stack) < 1:
                check =- 1
                break
            stack.pop()
    if len(stack) > 0 or check == -1:
        print("NO")
        check = 0
    else:
        print("YES")
    stack = []

달성 조건

Language	Memory	Time
Python3	31256 KB	44 ms