문제 설명

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

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

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

제한사항

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

입출력 예

s		result
"[](){}"	3
"}]()[{"	2
"[)(]"		0
"}}}"		0

입출력 예 설명
입출력 예 #1

• 다음 표는 "{}" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"[](){}"		O
1	"](){}["		X
2	"(){}[]"		O
3	"){}[]("		X
4	"{}[]()"		O
5	"}[](){"		X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"}]()[{"		X
1	"]()[{}"		X
2	"()[{}]"		O
3	")[{}]("		X
4	"[{}]()"		O
5	"{}]()["		X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

접근방법

우선 괄호 문제가 나오면 스택부터 생각해야 된다는 사실을 알게 되었다. 괄호와 스택은 LIFO라는 공통점을 가지고 있기 때문에 스택을 통해 해결이 가능한 문제이다.

우선 문자열을 리스트로 만들어 주고, chk라는 변수로 True, False를 판별하도록 하였다. 리스트를 순회하며 여는 괄호가 나오면 이를 tmp라는 스택에 넣어주고 닫는 괄호가 나오면 tmp를 pop한 문자와 현재 닫는 괄호를 비교하여 짝이 맞지 않을 경우 chk를 False로 바꿔주어 카운팅되지 않게 하였다. 한번의 순회가 끝나면 슬라이싱 기법으로 리스트를 한칸씩 밀리도록 갱신해주었다.

• 정답을 저장할 변수 answer를 0으로 정의한다.
• s의 길이만큼 반복해야 하므로 s만큼 반복하는 i에 대한 for문을 돌린다.
  -> s를 리스트로 바꾸어 s1에 저장해준다.
  -> 스택으로 사용할 임시 배열 tmp를 선언한다.
  -> chk변수를 선언하고 True로 저장해준다.
  -> s1을 순회하는 j에 대한 for문을 돌린다.
  --> 만약 j가 [, (, {중에 해당하면 tmp에 j를 넣어준다.
  --> 만약 j가 해당하지 않을 경우,
  ---> tmp가 비어있다면 chk를 False로 갱신하고 반복문을 종료한다.
  ---> tmp.pop()을 임시변수 x에 저장해준다.
  ----> 만약 j가 ]이고 x가 [가 아니라면 chk를 False로 갱신하고 반복문을 종료한다.
  ----> 만약 j가 )이고 x가 (가 아니라면 chk를 False로 갱신하고 반복문을 종료한다.
  ----> 만약 j가 }이고 x가 {가 아니라면 chk를 False로 갱신하고 반복문을 종료한다.
  -> 만약 tmp가 비어있지 않다면 chk를 False로 갱신한다. (짝이 안맞은 경우이므로)
  -> 만약 chk가 True라면 answer를 1 증가시킨다.
  -> s를 s[1:]+s[0]으로 갱신한다.
• answer를 반환한다.

solution.py

def solution(s):
    answer = 0
    for i in range(len(s)):
        s1=list(s[:])
        tmp=[]
        chk=True
        for j in s1:
            if j in ('[', '(', '{'):
                tmp.append(j)
            else:
                if not tmp:
                    chk=False
                    break
                x=tmp.pop()
                if j==']' and x!='[':
                    chk=False
                    break
                elif j==')' and x!='(':
                    chk=False
                    break
                elif j=='}' and x!='{':
                    chk=False
                    break
        if tmp:
            chk=False
        if chk:
            answer+=1
        s=s[1:]+s[0]
    return answer