[프로그래머스] 괄호 회전하기 / Python / 스택(Stack)

괄호 회전하기

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

풀이 방법

• 회전한 문자열(origin)을 앞에서부터 차례대로 꺼내어 빈 스택(stack)에 옮겨 담으면서 올바른 괄호 문자열인지 검사하는 방식으로 구현했다.
• stack이 비어있지 않은 경우에, 가장 상단에 있는 괄호가 닫는 괄호이면 올바르지 않은 괄호 문자열이므로 바로 종료한다. 가장 상단에 있는 괄호가 여는 괄호이면 origin에서 꺼낸 괄호와 비교하여 짝이 맞는지 검사한다. 짝이 맞다면 stack의 최상단 괄호를 pop하고 짝이 맞지 않는다면 꺼낸 괄호를 stack에 집어넣는다.
• origin이 빌 때까지 이를 반복한 후, stack이 비어있다면 올바른 문자열이다.

from collections import deque

def solution(s):
    answer = 0
    correct = {'{':'}', '[':']', '(':')'}
    
    for i in range(len(s)):
        origin = deque(s[i:] + s[:i])
        stack = []
        
        while origin:
            c = origin.popleft()
            if not stack:
                stack.append(c)
                
            else:
                if stack[-1] in ['}', ']', ')']:
                    break
                    
                elif correct[stack[-1]] == c:
                    stack.pop()
                    
                else:
                    stack.append(c)
                
        if not stack:
            answer += 1
            
    return answer