[프로그래머스] 올바른 괄호

문제

• 올바른 괄호면 true를, 올바르지 않은 괄호면 false를 리턴하기
  • 괄호가 올바르다는 것은 ( 로 열렸으면 ) 문자로 닫혀야 한다는 것
• 1 <= 문자열 s 길이 <= 100,000

 

풀이

• 시간 복잡도 : $O(N^2)$ 은 안된다.
• ( 로 시작하면 +1, 닫히면 -1 로 카운트 하기
  • 항상 양수여야 하고, 마지막에는 0이 되어야 한다

 

def solution(s):
    answer = True
    cnt = 0
    for i in s:
        if i == '(' :
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0 :
            break
    if cnt != 0 :
        answer = False
    return answer

 

References

• 프로그래머스 고득점Kit 스택/큐