백준 9012번 "괄호"

Question:

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

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

Input:

입력 데이터는 표준 입력을 사용한다.
입력은 T개의 테스트 데이터로 주어진다.
입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.
각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다.
하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

Output:

출력은 표준 출력을 사용한다.
만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

Restriction:

시간제한:
1초

Example Case:

Input case 1:
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

Output case 1:
NO
NO
YES
NO
YES
NO

Input case 2:
3
((
))
())(()

Output case 2:
NO
NO
NO

풀이 과정:

이 문제는 스택을 활용한 괄호 짝 맞추기 문제이다.
소스코드를 작성할 때, 컴파일러가 괄호의 짝을 맞춰주는 것을 경험해 본 적이 있을텐데
이는 자료구조중 스택을 활용한 기능이다.
예를 들어,
왼쪽 괄호(“(“)가 스택에 Push 된 후,
오른쪽 괄호(“)”)을 만나게 되면 Pop 연산을 진행한다.
연산이 다 끝난 후
size가 empty가 된다면 괄호의 짝이 다 맞는 상태이다.

간단하게 예시로,
ex) (((()))
이 경우에는 push 4번 - pop 3번이 일어나게 되는 것이다.

그런데,이와 같은 문제를 풀 때는 유의해야할 점이 두가지가 있다.
첫번째로,
결과적으로 스택의 size가 empty 상태가 아니게 되면,
괄호의 짝이 안맞는것이다.
두번째로,
연산을 진행 하는 중 스택의 size가 음수 상태가 된다면
이 또한 괄호의 짝을 맞출 수 없다.
(알맞는 왼쪽 괄호가 존재하지 않는다는 의미)
ex) ())(()
=index 2부분부터 이미 맞는 괄호가 없다.

이를 주의해서 단순연결리스트로 python 스택을 구현하였다.

class Node:
    def __init__(self,item,link):
        self.item = item
        self.next = link

def push(item):
    global top
    global size
    top = Node(item,top)
    size += 1

def pop():
    global top
    global size
    if size > 0: 
        top = top.next
        size -= 1
    else: #size가 0 이하가 되었을때,size 크기만 변화
        size -= 1

top = None #초기화
size = 0

import sys

N = int(sys.stdin.readline()) #sys.stdin.readline() 사용시 int형을 꼭 붙여주자. 안붙여주면 한줄 단위로 입력을 받아 개행문자가 같이 저장된다.
for _ in range(N):
    command = sys.stdin.readline().strip() #.strip()은 문자열을 받을 때 앞 뒤 개행문자를 제거해준다.
    for i in range(len(command)):
        if command[i] == "(":
            push("(")
        elif command[i] == ")":
            pop()
            if size < 0: #size가 음수가 되는 순간 성립하지 않는다. 따라서 연산을 중단하고 출력하면된다.
                break
        else:
            continue
    if size == 0:
        print("YES")
    else:
        print("NO")
        
    size = 0 #한줄씩 괄호 검사가 끝나고 나면 초기화를 해줘야한다!!(전역변수인걸 기억하자)
    top = None 

Conclusion:

sys.stdin.readline()을 사용할 때
순정 그대로 사용할 시 개행문자가 포함된다는 사실을 알아두자

• 백준
• 문제풀이