문제

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

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

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

풀이

아이디어

• 올바른 괄호 문제는 스택을 활용하는 것으로 너무 유명하니 더 긴 설명은 패스하겠다.
• s의 길이가 1,000 이하라서 len(s)번 반복문 돌리면서, 돌렸을 때마다 또 s를 스캔하는 O(N^2) 풀이가 가능했다.
• deque의 rotate(-1)을 이용해서 쉽게 왼쪽으로 회전시키는 것을 코드로 짧게 나타낼 수 있었다.
• 딕셔너리에 각 괄호의 짝꿍을 기록해놓음으로써 빨리빨리 찾을 수 있게 하였다.

코드

from collections import deque

MAP = {
    "]" : "[",
    ")" : "(",
    "}" : "{",
}

def solution(s):
    q = deque(list(s))
    
    def checkIsRight(s):
        stack = []
        for c in s:
            if c == '(' or c == '[' or c == '{':
                stack.append(c)
            elif len(stack) == 0 and (c == ')' or c == ']' or c == '}'):
                stack.append(c)
            elif len(stack) and (c == ')' or c == ']' or c == '}') and stack[-1] == MAP[c]:
                stack.pop()
                

        if len(stack) == 0:
            return True
        else:
            return False
    
    count = 0
    for x in range(0, len(s)):
        if checkIsRight(q):
            count += 1
        q.rotate(-1)
    
    return count