올바른 괄호

• stack/queue

문제 설명

괄호가 바르게 짝지어졌다는 것은 ‘(’ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다.

예를 들어 “()()” 또는 “(())()” 는 올바른 괄호입니다.
“)()(” 또는 “(()(” 는 올바르지 않은 괄호입니다.
‘(’ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

test_input = "(()())()"
test_output = True


def solution(s):
    n = len(s)

    # 뻔한 조건들 거르기
    if (s[0] == ")") or (n % 2 != 0) or (s[-1] == "("):
        return False

    # stack에 넣어주면 효율성 안나와서 count로 전환
    left_count = 0
    for c in s:
        if c == "(":
            left_count += 1
        else:
            if left_count == 0:
                return False
            left_count -= 1

    return left_count == 0


print(solution(test_input))

True

처음엔 실제 deque을 사용해서 popleft를 사용해서 비교를 해줬는데 이렇게 하면 효율성테스트2에서 자꾸 시간초과가 나서 count를 해주는 방식으로 바꿈. 아무래도 stack append, popleft, pop하는 방식보다는 그냥 한번 돌면서 숫자노름하는 것이 시간적으로는 훨씬 이득일 것 같긴하다.