Level 2 괄호 회전하기 Python 3

https://programmers.co.kr/learn/courses/30/lessons/76502?language=python3 

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

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_괄호회전하기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import deque
def solution(s):
    answer = 0
    str = deque(s)
    for _ in range(len(s)):
        str.append(str.popleft())
        stack = []
        i = -1
        while i < len(str)-1:
            i += 1
            if not stack:
                stack.append(str[i])
                continue
            if (str[i] == ']' and stack[-1] == '[') or (str[i] == ')' and stack[-1] == '(') or (str[i] == '}' and stack[-1] == '{'):
                stack.pop()
            else: stack.append(str[i])
        if not stack: answer += 1
    return answer

---

풀이 과정

풀이 시간 12분

괄호 회전은 deque을 사용해서 가장 왼쪽의 괄호를 pop해서 오른쪽으로 push하여 구현하였다.

그리고 올바른 괄호인지 판별하기 위해서 stack을 활용해서 stack의 top에 있는 괄호와 비교해서 현재 stack에 들어가야 하는 괄호와 한 쌍이면 stack의 top에 있는 괄호를 pop함으로써 괄호 쌍을 없애주었다.

stack이 비어있거나 stack의 top에 있는 괄호와 한 쌍이 아니라면 현재 탐색하고 있는 괄호를 stack에 담아주었다.

최종적으로 stack에 남아있는 괄호가 있는 경우, 올바른 괄호가 아니다는 것을 판별할 수 있다.

from collections import deque
def solution(s):
    answer = 0
    
    #문자열 s를 deque으로 바꿔준다
    str = deque(s)
    
    #0~len(s)-1번 괄호를 회전시킨다
    for _ in range(len(s)):
        str.append(str.popleft())
        
        #올바른 괄호인지 판별
        stack = []
        i = -1
        while i < len(str)-1:
            i += 1
            #stack이 비어있는 경우, 현재 괄호를 stack의 top에 쌓는다
            if not stack:
                stack.append(str[i])
                continue
            
            #stack의 top에 있는 괄호와 현재 괄호가 한 쌍인 경우, stack의 top에 있는 괄호를 pop해준다
            if (str[i] == ']' and stack[-1] == '[') or (str[i] == ')' and stack[-1] == '(') or (str[i] == '}' and stack[-1] == '{'):
                stack.pop()
                
            #한 쌍이 아닌 경우, 현재 괄호를 stack의 top에 쌓는다
            else: stack.append(str[i])
        
        #stack이 비어있는 경우, 올바른 괄호이므로 answer 카운팅
        if not stack: answer += 1
        
    return answer
    
#시간복잡도 = O(len(s)^2) -> O(n), 공간복잡도 = O(n)