이해

• 다음 규칙을 지키는 문자열은 올바른 괄호 문자열이라고 정의한다.
  • (), [], {}는 모두 올바른 괄호 문자열이다.
  • A가 올바른 괄호 문자열이면, (A), [A], {A}도 올바른 괄호 문자열이다.
  • A, B가 올바른 괄호 문자열이면, AB도 올바른 괄호 문자열이다.
• s가 매개변수로 주어질 때, s를 왼쪽으로 x(0 <= x < s의 길이)칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return하라.

계획

• 완전 탐색으로 접근한다. 가능한 모든 x값에 대해서 s를 x칸 회전시킨 문자열이 올바른 괄호 문자열인지 확인한다.
• s를 왼쪽으로 1칸 회전하는 함수를 구현한다.
• 주어진 문자열이 올바른 괄호 문자열인지 체크해주는 함수를 구현한다.
• 올바른 괄호 문자열인지 확인하는 방법
  • stack 자료구조를 사용해서 문자열 s에 속해있는 문자를 stack에 하나씩 푸시한다.
  • stack의 맨 위에 있는 두 개의 문자를 합친 문자열이 올바른 괄호 문자열일 경우에 두 개의 문자를 제거해 준다.
  • 문자열 s에 속해있는 모든 문자를 stack에 넣어준 후에 stack이 비어있을 경우 주어진 문자열이 올바른 괄호 문자열이 맞다.
• 시간 복잡도는 O(N^2)이다.

실행

def one_step_left(s):
    return s[1:] + s[0]

def is_right(s):
    stack = []
    for c in s:
        stack.append(c)
        if len(stack) >= 2 and stack[-2] + stack[-1] in ['()', '[]', '{}']:
            stack.pop()
            stack.pop()
    return True if not stack else False
    
    
def solution(s):
    count = 1 if is_right(s) else 0
    
    for _ in range(len(s) - 1):
        s = one_step_left(s)
        if is_right(s):
            count += 1
    return count

개선

• 문자열을 왼쪽으로 1칸 회전하는 방법이 매우 간단하므로 one_step_left 함수를 선언하지 않고 구현한다.
• 0칸 회전하는 경우는 굳이 따로 for문 밖에서 처리하지 않고 s의 길이만큼 회전하는 경우로 취급해서 for문 안에서 같이 처리하면 코드가 훨씬 깔끔해진다.

def is_right(s):
    stack = []
    for c in s:
        stack.append(c)
        if len(stack) >= 2 and stack[-2] + stack[-1] in ['()', '[]', '{}']:
            stack.pop()
            stack.pop()
    return True if not stack else False
    
    
def solution(s):
    count = 0
    for _ in range(len(s)):
        s = s[1:] + s[0]
        if is_right(s):
            count += 1
    return count

회고

• 계획을 잘 세워서 깔끔하게 잘 푼 것 같다.
• 만족스럽다.