📖 문제

📝 풀이 과정

1. 문자열의 길이가 홀수라면 올바른 괄호 문자열이 될 수 없으므로 0을 리턴
2. 입력으로 주어진 문자열 s를 0번 ~ (s의 길이 - 1)번 회전시키면서 i번 회전된 문자열이 올바른 괄호 문자열인지 확인한다.
3. 올바른 괄호 문자열인지 확인할 때 (함수 iscorrect())
   3-1. 문자열 s에 있는 모든 문자를 순회
   3-2. 만약 현재 문자가 여는 괄호('(','[','{')라면 stack에 넣는다.
   3-3. 만약 현재 문자가 닫는 괄호(')',']','}')라면 stack top을 검사한다.
   -> 맞는 짝이라면 pass, 맞는 짝이 아니라면 올바른 괄호 문자열이 아니므로 return False
   3-4. 문자열 순회가 끝난 후 stack이 비어있으면 올바른 괄호 문자열이므로 return True, stack에 문자가 남아있다면 return False

⌨ 코드

from collections import deque
# 올바른 괄호 문자열인지 확인
def iscorrect(s):
    stack = deque()
    open_ = ['(', '[', '{']
    close_ = [')',']','}']

    for c in s:
        # 3-2. c가 '(', '[', '{'중 하나인 경우
        if c in open_:
            stack.append(c)
        # 3-3. c가 ')',']','}'중 하나인 경우
        else:
            if not stack:
                return False
            elif c == close_[0]:
                if stack.pop() != open_[0]:
                    return False
            elif c == close_[1]:
                if stack.pop() != open_[1]:
                    return False
            else:
                if stack.pop() != open_[2]:
                    return False
    # 3-4
    if stack:
    	return False
    else:
    	return True

def solution(s):
    answer = 0

    if len(s) % 2 != 0:
        return answer

    for rotate_cnt in range(len(s)):
        if iscorrect(s):
            answer += 1
        # 문자열 회전
        s += s[0]
        s = s[1:]

    return answer

😊 느낀점

처음 문제를 받고 위의 풀이과정대로 문제를 풀면 시간복잡도가 O(N^2)이라서 효율적인 편은 아니니까 다른 방법이 없을까 고민하느라 푸는데 오래 걸렸다.
근데 제한사항에 문자열 s의 최대 길이가 1000이기 때문에 O(N^2)에 풀어도 됐었다.
블로그에 코드를 작성하면서 느낀 건데 문자열을 회전시키는 함수를 만들었으면 더 가독성 높은 코드였을 것 같다.