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

문제링크

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

프로그래머스

기존의 괄호 유효성문제의 상위문제인 것 같다.

문제 접근법.

1. 괄호 회전에 대한 처리

2. 괄호 유효성

 

괄호 회전은 queue를 통해 queue.popleft() 를 해주고 다시 그 것을 queue.append()해주면

회전이 된다 이것을 0번부터 len(s)-1번까지 해주면 괄호 회전은 완료이다.

 

이제 괄호 유효성검사를 해보았다.

괄호 유효성을 검사하는 방법은 stack을 사용한 풀이가 있다.

괄호가 왼쪽 즉, '[', '{', '(' 이 오면 반대로 ']' , '}', ')' 오른쪽을 stack에 넣어주고

오른쪽 괄호가 오면 stack의 길이가 0이 아님을 확인하고 pop한 것과 같으면 넘어가고

queue.pop()원소와 현재 괄호가 다르면 괄호 유효성이 유효하지 않게된다.

 

그리고 stack에 남아있는 원소가 없고 괄호 유효성에 영향을 끼치지 않았으면 정상적인 괄호이다.

아래는 코드 풀이입니다.

from collections import deque

def solution(s):
    answer = 0
    
    if len(s) == 1:
        return 0
    
    for i in range(len(s)):
        queue = deque(s)
        # check_num이 1이면 괄호유효 0이면 유효 x
        check_num = 1
        # 회전하고 괄호 유효성검사 popleft를 i 개수만큼하고 append해준다
        for j in range(i):
            tmp = queue.popleft()
            queue.append(tmp)
        # 횟수마다 회전 완료 괄호 유효성검사
        stack = []
        for k in queue:
            if k == '[':
                stack.append(']')
            elif k == '{':
                stack.append('}')
            elif k == '(':
                stack.append(')')
            else:
                if len(stack) == 0:
                    check_num = 0
                    break
                elif stack.pop() != k:
                    check_num = 0
                    break
        if check_num == 1 and len(stack) == 0:
            answer += 1
        
    return answer

 

회전과 괄효유효성을 동시에 하다보니 시간복잡도를 초과하지 않을까? 하는 걱정이 있었는데

해당 문제에서는 O(n^2)까지 시간복잡도를 사용할 수 있어 중간에 break를 하는 나의 풀이로 해결할 수 있었다.