9012 괄호

💡문제 분석 요약

• 괄호 문자열의 짝이 맞는지 분석한다. () 이것은 맞고 ()),  )( 이런 것은 틀리다.
• 문자열의 길이는 2~50이다.

💡알고리즘 설계

• 스택에 넣고 하나씩 빼면서 짝을 맞춰보기
• 또는, ( ) 개수를 보고 짝이 안맞으면 NO 출력

💡코드

from collections import deque
n = int(input())

for _ in range(n):
    dq = deque(input())
    compare = 0

    if dq.count("(") != dq.count(")"): # 괄호의 개수 자체가 다르면 비교 X
        print("NO")
        continue

    """
    (은 )보다 항상 많거나 같아야 한다는 것을 이용
    개수를 체크하면서 compare 값을 늘려서 음수가 된다면 ())와 같은 상황이므로 NO
    """
    for i in dq:
        if i == "(":
            compare += 1
        elif i == ")":
            compare -= 1
        if compare < 0:
            print("NO")
            break
    if compare == 0:
        print("YES")

💡시간복잡도

• 길이 N에 대해서만 for문을 돌리므로 O(N)이 될 것이다.

💡 틀린 이유

• 처음에는 (와 )의 짝을 반드시 맞춰야겠다고 접근했다. 예를들어 (를 보면 )이 나올때까지 진행하고 짝 맞으면 둘 다 pop 하고 .... 그런데 코드로 풀어나가니 잘 안되었다.

💡 틀린 부분 수정 or 다른 풀이

• 그런데 (와 )의 개수 자체로 접근하는 것이 좋아보였다. ( ) 이렇게 짝이 되려면 )의 개수가 절대로 (보다 높은 순간이 있어선 안되므로 )은 (보다 같거나 적게 로직을 작성해보았다.

💡 느낀점 or 기억할정보

• 스택을 이용한 풀이도 나중에 풀어보고, 정리하기
• 스택 문제라고 해서 꼭 스택으로만 풀리리란 법은 없었다.