백준 알고리즘: 9012번 괄호 (Python)

문제 정보

---

9012번: 괄호

 

 

핵심

---

무턱대고 열린 괄호 ( 와 닫힌 괄호 ) 의 개수를 세고 비교하지 않아야 한다

 

반례

())(()

괄호의 개수는 각각 같을 지 몰라도, 먼저 닫히고 나중에 열리는 것 또한 개수가 같아질 수 있기 때문이다

 

따라서 이 문제는 열린 괄호와 닫힌 괄호 한 쌍을 찾아가면서 풀이하는 것이 적절하며, 나는 약간 다른 방식으로 풀이하였다

 

풀이

---

import sys
T = sys.stdin.readlines()[1:]
for t in T:
    count = 0
    for i in t:
        if count == -1:
            break
        if i == '(':
            count += 1
        elif i == ')':
            count -= 1
    print("YES" if count == 0 else "NO")

count 변수를 두었는데 역할은 다음과 같다

count : 열린 괄호의 개수를 카운팅한다. 만약 닫힌 괄호를 만나면 count의 개수를 하나 빼 준다. 만약 count가 음수라면 괄호가 먼저 닫힌것으로 판단하고 NO 를 출력하고 break 시킨다

그러면 count는 -1인 상태로 아래 print() 를 접하게 되므로 NO 가 출력된다

count가 0이라면 열린 괄호와 닫힌 괄호가 순서에 맞게 잘 배열된것으로 확인하여 YES를 출력한다

 

 

고찰

---

또한 이 풀이도 한번 고려해볼 수 있다

import sys
T = sys.stdin.readlines()[1:]
for t in T:
    t = t.strip()
    while '()' in t:
        t = t.replace('()', '')
    print('NO') if t else print('YES')

어차피 괄호는 한 쌍 이상의 () 가 존재하게 되어있으므로 () 를 빈 문자열로 치환해주는 과정을 반복하면서 전체 문자열이 마지막에 비어있으면 올바른 괄호 문자열이 되고,

비어있지 않다면 올바르지 않은 괄호 문자열로 생각할 수 있을 것이다