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

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/76502

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

 

 

풀이

 

from collections import deque

def solution(s):
    s = deque(list(s))
    count = 0
    
    for i in range(len(s)):
        s.rotate()
        stack = []
        
        for par in s:
            if par == '(' or par == '{' or par == '[':
                stack.append(par)
            else:
                if len(stack) <= 0:
                    stack.append(0)
                    break
                    
                if par == ']' and stack[-1] == '[':
                    stack.pop()
                elif par == '}' and stack[-1] == '{':
                    stack.pop()              
                elif par == ')' and stack[-1] == '(':
                    stack.pop()
                    
        if len(stack) == 0:
            count += 1
                    
    return count

 

보자마자 deque에서 rotate 함수랑 stack 쓰면 되겠다라는 생각이 들었다.

로직은 다음과 같다.

 

1. s를 deque로 만들고 rotate함수로 돌리면서 외부 for문을 돌림

2. s가 한번 돌 때마다 내부 for문으로 문자를 하나씩 가져와서

   여는 괄호이면 stack에 넣고 닫는 괄호이면 stack의 최상위 값을 확인하고 매칭되면 뽑는다

3. 만약 닫는 괄호인데 stack이 비었다면 stack에 0을 추가하고 break

4. 내부 for문을 빠져나와서 stack이 비었다면 count + 1

---

 

시간 복잡도

 

O(N)

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

list의 빈 것 체크

 

if len(stack) <= 0:

 

은

 

if not stack:

 

과 같다.

 

 

고찰

 

기출이 최고