프로그래머스 2단계 - [괄호 회전하기]

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

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

1. 문제이해

 - 문자열 회전

 - 주어진 조건에 맞기위한 규칙 찾아내기

 

2. 코드 작성

import re

def solution(s):
    answer = 0
    for i in range(len(s)):
        s = s[1:] + s[0]
        ns = s
        length = len(ns)
        
        while True:
            ns = re.sub('\(\)', '', ns)
            ns = re.sub('{}', '', ns)
            ns = re.sub('\[]', '', ns)        
            if length == len(ns):
                break
            length = len(ns)

        if length == 0:
            answer += 1
    
    return answer

※ 시간복잡도

정규식으로 변환하는 라이브러리가 어떤 알고리즘으로 동작하는지 확인 필요.

만약 문자열을 순차적으로 탐색해서 제거하는 것이라면 위 알고리즘은 효율성에서는 떨어진다고 생각됨.

 

3. 풀이간 체크사항

 1) 과거 유사한 문제로 올바른괄호찾기(?) '(', ')' 로만 이루어진 문제가 있어 그와 비슷하게 풀이하려 했으나, ({)} 과

    같은 문제가 있어 다른 규칙을 찾고자 함.

 2) 위와같은 조건에 대해서는 () {} [] 와 열린기호와 닫힌기호가 붙어있는 모양이 존재할 수 밖에 없음을 생각.

 3) 모두 제거 될 때까지 변환하다보면 해당 문자열이 올바른 괄호 문자열 여부를 판단할 수 있음.

 4) 또 다른 방식으로는 {{()}}{[]} => {{()}} + {[]} => {()} + [] => () => '' 와 같이 재귀로 푸는 법을 생각해 보았으나 위의

    방식이 더 간단하다고 생각됨.

 

4. 단위 기능 체크

# 회전을 위한 코드
a = '1234'
a = a[1:] + a[0] #'234' + '1'

# deque 를 활용한 방법
from collections import deque
a = '1234'
a = deque(list(a))
a.rotate()