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

프로그래머스, 올바른 괄호

 

TL;DR

• 스택(Stack)

문제 분석

1. 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다.
2. '(' 또는 ')'로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를, 아니면 false를 반환하라.

 

- 1. 열린 괄호 뒤에 닫힌 괄호가 오는, 하나의 완성된 괄호 문자가 되었을 때를 올바른 괄호라고 문제에서 정의하고 있다.

- 2. 문제 조건에 따라 올바른 괄호로 구성되었는지 여부에 따라 True 또는 False를 반환한다.

입출력 형태

입출력 예시

- 결과가 True인 예시들은 모두 ()가 쌍을 이룬다.

- 결과가 False인 예시들은 () 쌍을 이루지 않는다.

풀이

def solution(s):
    answer = True
    _stack = []
    
    for c in s:
        if not _stack or c == '(': # 1
            _stack.append(c)
        else: # 2 
            top = _stack.pop() 
            if top != '(': 
                return False
    
    return len(_stack) == 0 # 3

 

- 스택(Stack) 문제의 대표적인 예시라고 할 수 있다. 

- 유사한 문제를 리트코드(https://firsteast.tistory.com/51?category=968702)에서 확인할 수 있으며, 이 문제는 보다 리트코드의 문제보다 조건이 적어 쉬운 문제라고 할 수 있다.

- 1. 스택이 비어있거나, 열린 괄호('(')일 때는 스택에 집어넣는다.

- 2 . 닫힌 괄호(')')일 때는 스택의 top을 확인해야 한다. 스택의 top이 열린 괄호 문자이면 넘어가고, 그렇지 않다면, 이 문자는 올바른 괄호가 아니므로 False를 반환한다.

- 3. 만약 올바른 괄호 문자라면 스택에 어떤 문자도 남아있으면 안 된다. 스택에 요소가 존재한다면, 다시 말해 스택의 길이가 0이 아니라면 올바른 괄호 문자가 아니다. 따라서 이를 반환한다.

 

개선된 풀이

def solution(s):
	return s.count('(') == s.count(')') and s.index('(') < s.index(')')

 

- 다른 사람들의 풀이를 구경하던 중 재밌는 풀이 방법이 있어서 확인해보려고 한다.

- 이 사람은 문자열 자체적으로 열린 괄호와 닫힌 괄호의 숫자가 같은지, 그리고 열린 괄호의 인덱스가 닫힌 괄호의 인덱스보다 작은데 위치해있는지를 반환하여 답을 구하고 있다.

- 기존의 스택이 아닌 새로운 방법이기에 인상 깊어서 기록을 남긴다.