[BOJ 9012] 괄호 (Python3)

www.acmicpc.net/problem/9012

9012번: 괄호

T=int(input())
array=[]
result=[]
for i in range(T):
    array.append(list(input()))
 
for i in range(T):
    right, left=[], []
    for j in range(len(array[i])):
        item=array[i].pop()
        if item==')':
            right.append(item)
        else:
            left.append(item)
            if len(right)!=0:
                left.pop()
                right.pop()
    if len(left)==0 and len(right)==0:
        print("YES")
    else:
        print("NO")

풀긴 풀었는데 정석대로 푼건 아니다. 그리고 메모리 낭비도 너무 심하다.

문자열을 뒤에서부터 뽑아서 닫는 괄호일 때는 right 배열에 넣어주고, 여는 괄호일 때는 left 배열에 넣어준 뒤 right 배열의 크기가 1 이상 즉 닫는 괄호가 있을 경우 여는 괄호에서 아이템 하나 빼주고, 닫는 괄호에서도 마찬가지로 아이템 하나 빼준다. 

이렇게 모든 문자열을 돌아 각 배열이 모두 0이면 YES, 아니면 NO 인 식으로 했다.

 

하지만 스택을 이용해서 더 쉽게 풀 수 있다.

velog.io/@polynomeer/BOJ-9012.-%EA%B4%84%ED%98%B8

BOJ 9012. 괄호

이 글을 참고하면, 문자열 앞에서부터 스택에 넣는다.

여는 괄호이면 스택에 넣고, 닫는 괄호이면 스택에서 아이템을 빼준다. (짝을 맞추기 위해서)

그렇게 해서 스택 크기가 0이면 YES, 아니면 NO를 출력한다.(짝에 맞지 않는 '(' 또는 ')'가 있다는 의미이므로)

여기서 주의할 점은 닫는 괄호가 더 많을 경우 NO를 출력하는 것이다.

스택을 이용해서 짝을 맞춰주는 방식(여는 괄호면 넣고, 닫는 괄호 만나면 빼주는 형식으로)으로 진행한다.

이때 저 글의 코드에서는 top=0으로 하여 여는 괄호면 top++, 닫는 괄호면 top--으로 하여 메모리 효율성을 높였다.