Today I Learned

오늘도 파이썬 코테코테

CT_괄호 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502

문제

(), {}, [] 처럼 올바로 괄호가 닫혀야 한다. {}[], ({})같이 서로 떨어져있어도 성립한다.
대괄호, 중괄호, 소괄호로 이루어진 문자열 s가 주어질 때, s를 왼쪽으로 x만큼 회전했을때 s가 올바른 괄호 문자열이 되게하는 x의 개수를 return해라.
1<= s <= 1000

s="[](){}" / result = 3

풀이 과정

• 이런 괄호문제는 일반적으로 stack을 활용해서 맞는 짝을 찾는다. python이니 deque를 import해서 stack으로 활용해 문제를 풀었다.

• 먼저 문자열이 올바른지 확인하는 함수를 만든다. 괄호끼리 쌍을 맞춰주기 위해 dict로 key와 value에 매칭시켜서 괄호 쌍을 넣는다.

• 문자열 하나씩 반복문을 돌면서 value에 있으면(열리는 괄호면) 스택에 넣고, key에 있으면(닫히는 괄호면) 스택에서 꺼내서 짝이 맞는지 확인한다. 이때 스택이 비어있으면(not stack 상태) 당연히 false를 반환한다. 그리고 문자열을 다 확인했을 때 스택이 비어있어야 올바르므로 True를 반환하게 return not stack으로 반환한다.

• solution 함수에선 반복문으로 문자열을 회전(s = s[1:] + s[0]) 시키면서 is_valid 함수가 True면 answer를 1씩 늘리면서 답을 찾아 반환한다.

Python 코드

from collections import deque

def is_valid(s):
    stack = deque()
    matching = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in matching.values():
            stack.append(char)
        elif char in matching.keys():
            if not stack or stack.pop() != matching[char]:
                return False
    return not stack

def solution(s):
    answer = 0

    for _ in range(len(s)):
        s = s[1:] + s[0]
        if is_valid(s):
            answer += 1
            
    return answer