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

https://programmers.co.kr/learn/courses/30/lessons/12909

스택을 이용해서 풀이 가능한 전형적인 문제이다. 나는 직접 스택을 구현해서 풀이했지만, 프로그래머스 스터디 리더님께서는 스택을 직접 구현하지 않고 변수를 활용해서 풀이하셨다. 어쨌든 스택의 원리를 이용한다는 점에선 풀이 접근에 변함이 없다. 직접 구현하면서도 이렇게 푸는 것보다 더 나은 방법이 있겠다 싶었지만...나는 직접 구현하는 게 좀 더 직관적이라 매번 그렇게 푸는 것 같다. pop, push 연산을 수행하는 것보단 변수만으로 구현하는 게 효율성 면에서 낫다. 특히, 공간 복잡도 면에서 더욱 그럴 것이다.

def solution(s):
	answer = True
    c = 0
    
    for char in s:
    	if char == '(':
        	c += 1
        else:
        	c -= 1
        if c < 0:
        	return False
    
    return c == 0
    
    
 ## 스택을 이용한 풀이
 
def solution(s):
    answer = True
    stack = []
    
    for char in s:
        if not stack:
            stack.append(char)
        else:
            top = stack.pop()
            if top + char != '()':
                stack.append(top)
                stack.append(char)
                

    return len(stack) == 0

확실히 stack을 이용한 것보다 변수를 이용한 풀이가 조금 더 깔끔하다. stack을 이용한 풀이는 stack을 따로 선언해야 하기 때문에 메모리를 더 차지할 수 밖에 없다. 즉, 공간 복잡도가 증가한다. 하지만 stack을 직접 구현하지 않고 stack의 원리만 이용하여 어떻게 보면 stack의 length만 판별하는 형식으로 풀이를 전개할 수 있다. 이런 부분은 내가 놓쳤던 부분이었던 것 같다.