괄호 회전하기

문제 안내

문제 설명

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

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

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

제한사항

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

입출력 예

	s = "[](){}"	  → result = 3
	s = "}]()[{"      → result = 0
	s = "[)(]"        → result = 0
    s = "}}}"         → result = 0

풀이

Code

from collections import deque

def check(s):
    # stack으로 활용할 빈 리스트 생성
    stack = []

    # s의 맨 앞의 요소를 꺼내와서
    for i in s:
        # 여는 괄호인 경우에는
        if i in ["[", "{", "("]:
            # sttack에 추가
            stack.append(i)
        # 그렇지 않고 닫는 괄호인 경우에는 경우를 나눠서 생각
        # 닫는 괄호가 대괄호인 경우에는
        elif i == "]":
            # stack에 괄호가 있고, 제일 끝에 있는 괄호가 여는 대괄호인 경우에는
            if stack and stack[-1] == "[":
                # 현재 닫는 괄호를 stack에 넣으면 둘이 짝이 맞기 때문에 제거해야 됨
                # 굳이 닫는 괄호를 stack에 넣었다 함께 제거할 필요 없이
                # 닫는 괄호만 제거
                stack.pop()
            # 그렇지 않은 경우(stack이 비었거나, 제일 끝에 있는 )
            else:
                return 0
        elif i == "}":
            if stack and stack[-1] == "{":
                stack.pop()
            else:
                return 0
        elif i == ")":
            if stack and stack[-1] == "(":
                stack.pop()
            else:
                return 0
            
    # 모든 작업을 완료했는데도 stack에 남은 괄호가 있으면 올바른 괄호 문자열이 아니기 때문에 0을 반환
    return 0 if stack else 1
    
def solution(s):
    # 자료형을 회전시켜야 하기 때문에 deque 함수를 통해 덱으로 변환
    s = deque(s)
    # 올바른 괄호 문자열인지 체크할 변수를 할당하여 초기 값을 0으로 셋팅
    cnt = 0
    # 문자열의 길이만큼 회전시키면서 올바른 괄호 문자열인지 확인
    for i in range(len(s)):
        # check 함수를 통해 나온 값을 추가해줌. (올바른 괄호 문자열이면 결과값이 1, 아니면 0)
        cnt += check(s)
        # 확인 후 문자열을 왼쪽으로 1칸만큼 회전
        s.rotate(-1)
    return cnt