프로그래머스 / 스택 / 괄호 회전하기

문제

---

 

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

프로그래머스

 

입출력

---

 

해설

---

 

해당 문제는 전에 풀이했던 올바른 괄호의 확장판 느낌의 문제이다.

 

이번에는 들어올 수 있는 괄호 문자가 총 3가지로 다음과 같다.

"{}", "()", "[]"

 

그렇기 때문에 if문을 통해서 구현해도 좋지만 해시맵을 이용해서 풀이를 진행하면 깔끔하게 구현할 수 있기 때문에

해시맵을 사용하였다.

 

괄호를 회전하는 것은 방법이 여러가지가 있을 수 있지만 필자는 deque를 이용하여 O(1)에 회전하는 방식을 구현하였다.

파이썬에는 rotate라는 함수를 통하여 pop_front, push_back의 느낌을 낼 수가 있다.

 

그리하여 회전을 하면서 올바른 괄호 쌍인지 판단내렸다.

 

 

정답코드

---

'''
'25. 08. 24

1. 올바르게 짝지어진 괄호
2. 1 <= |S| <= 1000일 때
S의 값을 왼쪽으로 쉬프트 했을 때 올바르게 짝지어진 괄호 문자열이 되게 하는 x의 개수를 return하여라.

ex)
    ()[]{} x = 0 만족
    x는 0부터 5까지만 가능, 0일 때만 만족한다. 아니지
    []{}() x = 2, 
    {}()[] x = 4 총 3번 가능

1. 왼쪽으로 쉬프트 하는 방식 O(1)에 가능
2. 올바른 괄호인지 판단하는 방법 O(|S|)에 판단 가능
3. 총 왼쪽으로 쉬프트하는 횟수 |S| - 1번

쉬프트 하면서 올바른 괄호 판단하는 시간 복잡도 => O(|S|^2) 10^6 이므로 충분히 N^2으로 돌려도 됨.

'''
from collections import deque
def is_right(word: deque) -> bool:
    s = []
        
    other = {']' : '[', '}' : '{', ')' : '('}
    for ch in word:
        if ch in '[({':
            s.append(ch)
        #빼내야 함.
        else:
            #스택의 맨 위가 쌍을 이루는 괄호인지 판별
            if s and s[-1] == other[ch]:
                s.pop()
            #아니면 끝내기
            else:
                return False
    if s:return False
    return True

def solution(s):
    answer = 0
    dq = deque([*s])#디큐에 넣어 놓는다.
    
    #쉬프트 횟수는 deque_len번 => 변경 후 체크할 거기 때문에
    for _ in range(len(dq)):
        dq.rotate(-1)
        answer += is_right(dq)
    return answer

 

깃허브 : https://buly.kr/8TrDAid

유튜브 : https://youtu.be/VWhQE9YqZtw