[Python] 프로그래머스 코딩테스트 연습 level2 (괄호 회전하기)

1. 문제 설명

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

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

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

 

 

 

 

 

2. 제한 사항

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

 

 

 

 

 

 

 

3. 내 풀이

from collections import deque
def solution(s):
    answer = 0
    s= deque(s)
    s.rotate(1)
    left = ['[', '(', '{']
    right = [']',')', '}']
    for i in range(len(s)):
        s.rotate(-1)
        stack = []
        answer += 1
        for x in s:
            if x in left:
                stack.append(x)
            elif left[right.index(x)] not in stack:
                answer -= 1
                break
            elif left[right.index(x)] == stack[-1]:
                stack.pop()
            else:
                answer -=1
                break
        if stack != []:
            answer -=1
    return max(answer,0)

1. 문자열을 deque로 선언 (rotate()함수 이용하기 위함)

2. 왼쪽에 있어야하는 '(', '[', '{' 문자열을 담은 left 리스트로 생성

3. 오른쪽에 있어야 하는 ')', ']', '}' 문자열을 담은 right 리스트로 생성

4. s의 문자 개수 만큼 반복 -> 반복마다 rotate(-1), stack 생성, answer +1

5. 각 반복으로 새로 생성된 deque를 x로 반복

6. 만약 x가 left 리스트에 존재한다면 stack에 추가

7. x가 right 리스트의 원소이지만 x의 짝꿍이 stack에 존재하지 않으면 answer -1 한 뒤 break

-> ex) '(]'

8. x의 짝꿍이 right 리스트의 원소이고 x의 짝꿍이 stack의 마지막 원소가 아니라면 answer -1 한 뒤 break

-> ex) '([)' 

9.  x의 짝꿍이 right 리스트의 원소이고 x의 짝꿍이 stack의 마지막 원소라면 stack 마지막 원소를 pop하여 삭제

10. 마지막으로 stack에 원소가 남아있으면 answer -1

-> ex) '{{{}' 방지 

 

 

 

 

 

4. 다른 사람 풀이

def is_valid(s):
    stack = []
    for ch in s:
        if not stack:
            stack.append(ch)
        elif stack[-1] == '(':
            if ch==')': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '{':
            if ch=='}': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '[':
            if ch==']': stack.pop()
            else: stack.append(ch)

    return False if stack else True

def solution(s):
    answer = 0
    for i in range(len(s)):
        answer += is_valid(s[i:]+s[:i])
    return answer