백준 - 괄호(9012)

www.acmicpc.net/problem/9012

9012번: 괄호

괄호의 조합들을 입력받았을 때, 쌍이 제대로 맞으면 'YES', 아니면 'NO를 출력하는 문제이다.

 

* 힌트

1. 스택의 개념을 사용한다.

 

* 풀이

end = 0

1. 입력을 받아 차례로 스택에 넣는다.

2. 스택의 원소들을 하나씩 pop하며 아래 조건에 따른다.

  1) pop한 원소 = ')'

     : end + 1 을 해준다.

  2) pop한 원소 = '('

     : end - 1을 해준다.

  3) end <0일 경우 break

3. for문이 끝났을 때 end가 0인지 확인한 후 0이면 'YES', 아니면 'NO'를 출력한다.

 

해당 문제는 알고리즘 문제에 자주 등장하는데, 스택의 개념을 활용해서 풀 수 있다는 것을 처음 알았다.

 

import sys
r = sys.stdin.readline

n = int(r())
# (이면 end - 1
# )이면 end + 1
# 두번째 for문 내에서 end 가 0보다 작아지면 No를 출력하고, 마지막에 end가 0인지 확인한다.
for i in range(n):
    string = list(r().strip())
    end = 0

    for i in range(len(string)):
        x = string.pop()
        if x == ')':
            end += 1
        else:
            end -= 1
        if end <0:
            break
    if end !=0:
        print('NO')
    else:
        print('YES')