[Queue, Stack] 프로그래머스 lv2. 괄호 회전하기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

 

 

---

설계 및 코드✨

가장 먼저 떠올렸던 아이디어는 회전을 위해 큐를 사용하는 것과

괄호가 순서대로 있어야 올바른 괄호 문자열이 된다는 것이었다. 

그런데 괄호가 순서대로만 있다고 올바른 괄호 문자열이 되는 것은 아님을 발견했다.

[{]} 이런 반례예시가 존재하기 때문이다!

그렇기 때문에 나는 큐와 스택 모두를 사용하는 방식을 선택하였다. 

 

큐를 순회하다가 여는 괄호가 나오면 여는 괄호에 해당하는 닫는 괄호를 스택에 추가, 
닫는 괄호가 나오면 스택의 top과 현재 큐 원소와 비교하여 같으면 넘어가고, 아니면 break 하도록 설계했다. 
여는 괄호에 해당하는 닫는 괄호를 연결해주기위해 딕셔너리를 사용했다.

 

# 큐사용
# 괄호 순서대로 있을 때 )( X 
# [{]} 이런 경우는 어떻게? => 스택과 큐 둘다 이용
# 큐를 순회하다가 여는 괄호가 나오면 스택에 추가, 
# 닫는 괄호가 나오면 스택의 top과 현재 큐 원소와 비교하여 같으면 넘어가고, 아니면 break
# 일단 완성시키고, 시간 줄이기

from collections import deque
def solution(s):
    answer = 0
    queue = deque(s) # 큐 사용 
    
    # 회전
    for i in range(len(queue)): 
        x = queue.popleft()
        queue.append(x)
        
        stack = []
        
        openclose = {'{':'}', '(' : ')' , '[':']'}
        for q in queue: # 큐 순회
            if q in ['{', '(', '[']:
                stack.append(openclose[q])

            elif q in ['}', ')', ']']:
                if stack:
                # 스택의 탑 -> stack[-1] 의미
                    if stack[-1] == q:
                        stack.pop()
                    else:
                        break
                else:
                    stack.append(q)
                    break
                        
                
        if len(stack) == 0:
            answer += 1
        
                    
    
    return answer