프로그래머스 올바른 괄호 파이썬 풀이

올바른 괄호 (Lv.2)

문제 요구사항

• '(', ')' 로만 구성된 문자열이 주어졌을 때, 올바른 괄호 여부를 True, False로 return 해야 한다.
• 올바른 괄호 정의
  • '(' 문자로 열렸으면 반드시 짝지은 ')'로 닫혀야 한다.
  • 올바른 괄호 예
    • ()(), ((()))(), (())
  • 올바르지 않은 괄호 예
    • ))((, (()))(, ((, ))

문제 접근

1. left and right

문제에서 주어진 요구사항을 보면, 올바른 괄호의 형태를 크게 두 가지로 나눌 수 있다.

1. ()
   '(' 바로 오른쪽에 ')'가 오는 경우
2. (())
   '(' 가 나오고 하나의 올바른 괄호 끝에 ')'가 오는 경우

처음 문제를 봤을 때는 이 두 가지 경우만을 생각하고
'('의 인덱스를 left, s 문자열 끝의 인덱스를 ')'로 두고

...
if s[left] == '(' and s[left+1] == ')':
	left+=2
    
elif s[left] == '(' and s[right] == ')':
	left += 1
    right -= 1
else:
	return False
...

처럼 코드를 작성했는데, 짜고보니 ()(()) 와 같이 여러 괄호가 붙어있는 형태를 고려하지 않은 접근이었다.
정확한 right를 찾으려면 완전탐색을 해야 하므로 다른 접근 방법을 생각했다.

2. 재귀?

가장 안 쪽에 있는 괄호부터 풀려면 재귀의 스택 구조를 이용해 풀 수 있을 것 같았지만
문자열의 길이가 최대 100,000 이므로 파이썬 recursion limit에 걸릴 것이다.

3. +1, -1

스택 구조를 이용하는 것도 편리하겠지만, 요구사항을 조금 더 단순하게 생각해보자.
올바른 괄호가 되려면 다음 두 가지 조건만 만족하면 된다.

1. '('가 오기 전에 ')'가 나오면 안된다.
2. 전체를 봤을 때 '('와 ')' 짝이 맞아야 한다.

이제 '('를 1, ')'를 -1로 대입하고 위 조건을 만족하도록 간단한 코드를 작성하면 된다.

코드

def solution(s):
    r = 0
    
    for c in s:
        if c == '(':
            r += 1
        elif c == ')':
            r -= 1
        if r < 0:
            return False
    return r == 0