[파이썬] 프로그래머스 월간 코드 챌린지 시즌 2 - 괄호 회전하기

 

문제 설명

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

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

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

---

제한사항

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

---

입출력 예sresult

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

 

풀이

 

def is_right(s):
    stack = []
    e_list = [']', '}', ')']
    dic = {"[": "]", "{": "}", '(': ')'}
    for i in s:
        if len(stack) <= 0 and i in  e_list:
            return False
        if len(stack) <= 0:
            stack.append(i)
        elif stack[-1] not in dic:
            return False
        elif i == dic[stack[-1]]:
            stack.pop()
        else:
            stack.append(i)
    if len(stack) == 0:
        return True
    else:
        return False

def solution(s):
    answer = 0
    for i in range(len(s)):
        if i == 0:
            if is_right(s) == True:
                answer += 1
        else:
            s = s[1:] + s[0]
            if is_right(s) == True:
                answer += 1
    return answer

풀이

함수 하나 만들어서 string 바꿀 때마다 올바른 괄호인지 체크해주었다. 예전에 자료구조에서 스택할 때 배웠던 거랑 비슷해서 스택을 사용했다.

if len(stack) <= 0 and i in  e_list:
            return False

이 부분을 처음엔 안 넣고 작성했는데 그렇게 하니까 다 시간이 너무 오래 걸리는 편이라서 효율성을 좀더 높여보려고 추가해주었다. 어차피 [, {, ( 가 ], }, ) 보다 무조건 먼저 들어와야 올바른 괄호라서 빈 스택에 뒤에 세 개가 먼저면 바로 False 반환하도록 했다.

처음에 딕셔너리를 사용해서 코드를 작성했다가 리스트 인덱스를 사용하는 방법도 생각을 해봤는데 코드를 돌려보니까 효율성 면에서 크게 차이가 없길래 그냥 그대로 놔뒀다.