[파이썬/알고리즘] 프로그래머스 - 올바른 괄호 (스택)

[문제]

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

[풀이]

def solution(s):
    stack = []
    for i in s:
        if i == "(":
            stack.append(i) 
        else:
            if stack == []:
                return False
            else:
                stack.pop() 
                
    return stack == []

 

stack = [ ]

stack을 선언한다.

 

for i in s:

's' 라는 문자열 길이만큼 반복문을 돌린다.

 

if i == " ( ":

     stack.append(i)

만약 ' ( ' 이 들어오면 stack에 넣는다.

 

else:

반대로 ' ) ' 이 들어왔을 때

 

if stack == [ ]:

   return False

stack이 비어있다면 ' ) ' 닫히는 것만 들어왔다는 것으로 ' ( ) ' 이 성립 안되기 때문에 False를 반환한다.

 

else:

    stack.pop()

stack이 비어있지 않다면 여는 괄호 ' ( ' 가 있었다는 것으로 ( ) 한 쌍이 완성되므로 ' ( ' 를 지워준다.

 

return stack == [ ]

최종적으로 stack이 비어있다면 모든 쌍이 완성되었다는 의미로 True를 반환하게 된다.

하지만 비어있지 않다면 False를 반환하게 된다.

 

예를 들어 '( ( (' 만 들어오면 쌍이 완성되지 않고 stack에는 '( ( (' 이 쌓여있기 때문에 비어있을 수가 없다.

따라서 False를 반환하게 된다.

 

[스택 설명 및 문제 접근 방법]

 

스택은 LIFO(Last in First Out)으로 가장 마지막에 들어간 것이 가장 먼저 나오는 것이다.

 

stack.pop() 하면 가장 마지막에 있는 원소를 제거한다.

 

stack[-1] 하면 가장 마지막에 있는 원소를 가져오기만 한다. 

 

순서 중에서 가장 최근 값만 기억하면 되는 문제나 최근 값 이전의 문제도 기억해야 하는 문제에서 스택을 사용한다.

'제일 위의', '제일 오른쪽의', '제일 최근에 쌓은' 이라는 개념이 들어가면 스택으로 접근한다.