Programmers - 괄호 회전하기[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/76502

코딩테스트 연습 - 괄호 회전하기

문제 설명

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

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

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

 

제한사항

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

 

입출력 예

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

 

입출력 예 설명

입출력 예 #1

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

 

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

 

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"[{}]()"	O
5	"{}]()["	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

---

문제 풀이

큐와 스택을 활용하여 문제를 풀 수 있다.

스택을 활용한 이유는 가장 마지막 열린 괄호(e.g. '(', '[', '{' )가 가장 먼저 닫혀야 하기 때문이다.

 

예를 들어 s = [()]인 상황이라고 가정해보자. 

s에서 문자를 앞에서부터 순차적으로 pop 하여 stack에 저장한다. 때문에 s는 큐의 구조가 적합하다.

위의 구조가 올바른 괄호인지 판별하기 위해선 s라는 큐와 arr이라는 스택이 있다고 가정할 때 과정은 아래와 같다.

 

step 0 : arr(stack)을 빈 리스트 s를 queue로 초기화한다.

s(queue)	'[',  '(',  ')',  ']'
arr(stack)

 

step 1 : s에서 가장 앞에 위치한 괄호가 열린 괄호('[') 이므로 pop 하여 stack에 push 한다. 

s(queue)	'(',  ')',  ']'
arr(stack)	'['

 

step 2 : s에서 가장 앞에 위치한 괄호가 열린 괄호('(') 이므로 pop하여 stack에 push한다. 

s(queue)	')',  ']'
arr(stack)	'[',  '('

 

step 3 : 스택의 가장 마지막 괄호('(')와 큐의 가장 앞의 괄호 (')')가 매칭 되므로 stack의 가장 마지막 괄호를 pop 한다.

s(queue)	']'
arr(stack)	'[',

 

step 4 : 스택의 가장 마지막 괄호('[')와 큐의 가장 앞의 괄호 (']')가 매칭 되므로 stack의 가장 마지막 괄호를 pop 한다.

s(queue)
arr(stack)

만약 입력 s가 올바른 괄호라면 최종적으로 스택과 큐는 모두 비게 된다. 따라서 큐와 스택이 모두 비었다면 count를 1 증가시킨다.

 

만약 위 과정에서 큐의 가장 앞의 괄호가 닫힌 괄호(e.g. ')', ']', '}') 일 때 스택의 가장 마지막 괄호와 매칭 되지 않는다면 올바른 괄호가 아니므로 괄호를 한 칸 더 회전하고 위 과정을 반복한다.

구현 코드

코드 링크 : 괄호 회전하기

from collections import deque
import copy

def solution(s):
    answer = 0
    q = deque(s)
    close = [')', ']', '}']
    open = ['(', '[', '{']
    
    for _ in range(len(s)):
        c = q.popleft()
        q.append(c)
        new_q = copy.deepcopy(q)
        arr = []
        while new_q:
            # 올바른 괄호 조건에 맞는지 판별
            if new_q[0] in close:
                if len(arr) == 0:
                    break
                if arr[-1] == open[close.index(new_q[0])]:
                    new_q.popleft()
                    arr.pop()
                else:
                    break
            elif new_q[0] in open:
                char = new_q.popleft()
                arr.append(char)
        # 큐와 스택이 모두 비었다면 올바른 괄호이므로 answer 1증가     
        if len(arr) == 0 and len(new_q) == 0:
            answer += 1
            
    return answer