[프로그래머스] 괄호 회전하기(python)

문제

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

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

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

 

 

제한조건

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

 

 입출력 예

 

 

 

 

풀이

 이 문제는 {},[],() 세 종류의 괄호로 구성된 문자열 s를 입력받아 해당 문자열에서 몇 개의 올바른 괄호가 나오는지를 찾는 문제입니다.

1번째 입출력 예시

위의 예시를 보게 되면 원래 입력받은 문자열에서부터 올바른 괄호인지 확인한 다음 괄호를 하나씩 회전하면서 올바른 문자열인지 확인합니다. 여기서 코드 구현을 위해 해야 할 것은 아래와 같습니다.

 

1. 입력받은 문자열을 회전시킬 수 있는 어떠한 곳으로 옮긴다. -> 여기서는 회전 및 스택 사용을 위해 deque를 이용

2. 스택을 이용하여 괄호의 짝이 맞는지를 확인 후 맞으면 True, 맞지 않을 경우 False를 반환한다.

3. 위의 과정을 입력받은 문자열의 길이만큼 반복해주고, 올바른 괄호가 몇개인지 반환한다.

 

이것을 코드로 구현하면 다음과 같습니다.

from collections import deque


# 문자열을 deque로 받아 deque를 rotate 시킴
def solution(s):  
    count = 0
    deq = deque()
    for i in s:
        deq.append(i)
    
    for _ in range(len(s)):
        if check(deq) == True:
            count += 1
        deq.rotate(-1)
    
    return count
    

# deque 내 괄호의 짝이 맞는지를 확인하는 함수
def check(s):
    chk = []
    for i in s:
        chk.append(i)
        if len(chk)>=2:
            if(chk[-1] == ']' and chk[-2] == '['):
                chk.pop()
                chk.pop()
            elif(chk[-1] == ')' and chk[-2] == '('):
                chk.pop()
                chk.pop()
            elif(chk[-1] == '}' and chk[-2] == '{'):
                chk.pop()
                chk.pop()
    
    if chk:
        return False
    else:

 

이렇게 해주면 모든 테스트를 정상적으로 통과하는 것을 확인할 수 있습니다.

 

 

+ 저는 풀이에 deque를 사용하였지만, deque를 사용하지 않고 스택 자체를 회전하는 함수를 직접 만들어 작성하는 방법으로 풀이를 진행해도 괜찮을 것 같다는 생각이 들었습니다. 아래는 스택 자체를 회전시키는 함수이니 참고 바랍니다.

def rotate_stack(stack):
    stack_size = len(stack)
    
    if stack_size <= 1:
        return stack
    
    for _ in range(stack_size):
        stack.append(stack.pop(0))
        print(stack)
    
    return stack