스택 - 프로그래머스 올바른 괄호 (파이썬)

코딩테스트 연습 - 올바른 괄호 | Programmers School

프로그래머스

 

 

def solution(s):
    isTrue=False
    stack=[]
    
    if s[0]=="(":
        stack.append(s[0])
    else:
        return isTrue
    
    for i in range(1, len(s)):
        if s[i]=="(":
            stack.append(s[i])
        else: 
            if len(stack)==0:
                return isTrue
            stack.pop()
            
    if len(stack)==0:
        isTrue=True
    return isTrue

 

 

스택 자료구조를 생각하고 풀었다.

파이썬에서는 일반적인 리스트와 pop() 메서드를 통해서 스택을 구현할 수 있다.

어려운 점은 없었고, stack.append(s[i]) 해야 하는데 stack.append(i)라고 작성하는 실수가 있었다. 

 

 

 

+ 왜 처음에 스택을 써야겠다고 생각했을까?

 

괄호들을 리스트에 추가한다고 했을 때,  왼쪽 괄호 하나 오른쪽 괄호 하나가 딱 매칭이 될 때 리스트에서 빼내야 하는데, 

큐로 하면 가장 마지막에 추가되는 ) 오른쪽 괄호와, 가장 먼저 추가된 ( 왼쪽 괄호가 함께 빠진다. 

문제 풀기 전이라 확신은 없었지만 이렇게 짝을 지어서 제거한다고 해도 틀린 괄호가 남을 가능성을 완전히 배제할 수 없을 것 같다고 생각했다.

 

스택으로 하면 가장 마지막에 추가되는 ) 오른쪽 괄호와, 가장 마지막에 추가되어서 스택의 가장 위에 있는 ( 왼쪽 괄호가 함께 제거될 수 있기 때문에 이 작업의 반복이 정상적으로 되었다면 무조건 올바른 배열의 괄호일 수밖에 없다.