99클럽 TIL (240818)

> [Middler] 괄호 회전하기

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

 

 

문제 풀이 과정

우선s를 회전시킬 때마다 모든 문자열이 쌍을 이루는지 확인해야 한다. 그래서 그 갯수를 카운트하여 리턴하면 된다. 그래서 아래처럼 동작하는 로직을 구성했다.

 

1. s를 돌면서 맨 앞 요소를 빼고 맨 뒤로 넣어 queue를 구성한다.

2-1. 만들어진 queue를 순회하면서 순차적으로 요소를 stack에 넣는다.

2-2. stack의 top요소와 top-1 요소가 쌍을 이룬다면 쌍을 모두 pop() 한다.

2-3. stack 요소가 없다면 쌍을 모두 이룬 것이므로 cnt +1 한다.

 

문제 풀이

python

from collections import deque
def solution(s):
    cnt = 0
    q = deque(s)
    for i in range(len(s)) :
        stack = []
        for j in range(len(s)) :
            stack.append(q[j])
            if stack :
                if ((stack[len(stack)-1] == "]" and stack[len(stack)-2] == "[")
                    or (stack[len(stack)-1] == ")" and stack[len(stack)-2] == "(")
                    or (stack[len(stack)-1] == "}" and stack[len(stack)-2] == "{")) :
                    stack.pop()
                    stack.pop()
        
        if len(stack) == 0 : cnt += 1
            
        front = q.popleft()
        q.append(front)
    
    return cnt

 

시간복잡도 O(N^2)

N이 1000이하이기 때문에 이중 반복문도 시간 초과되지 않는다.

 

회고 및 느낀점

쌍을 비교하는 것을 저렇게 비교하였으나 좀 더 효율적인 방법이 있지는 않을까? 고민해보자