[알고리즘] 프로그래머스 괄호 회전하기 - Python

문제 : 프로그래머스 괄호 회전하기 문제

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

프로그래머스

 

이 문제도 스택을 활용하는 문제이다. 가장 단순한 괄호 스택 문제와는 살짝 다른 점이 회전이 가능하다는 점이다.

문제 본문에 있는 A, B 예시를 보며 생각한 것이 회전을 하면서 완전한 괄호의 개수를 세면 답이 나온다는 점이었다. 이걸 활용해서 푼 것이 아래의 풀이이다. 

 

def solution(s):
    answer = 0
    stk=[]
    l=len(s)
    i=0
    while i <=l*2 and i<len(s):
        if s[i]=='{' or s[i]=='[' or s[i]=='(':
            stk.append(s[i])
        elif len(stk)>0:
            if (stk[-1]=='[' and s[i]==']') or (stk[-1]=='(' and s[i]==')') or (stk[-1]=='{' and s[i]=='}'):
                stk.pop()
                if len(stk)==0:
                    answer+=1
            else:
                return 0
        else:
            if i<l:
                s=s+s[i]
            else:
                return 0
        i+=1
    if len(stk)>0:
        return 0
    return answer

 

이렇게 구현을 하면서 헷갈렸던 점은 아래와 같다.

• 괄호의 회전을 문자열 s의 연장으로 풀어나간 점
• 괄호의 회전과 괄호 완전한지 여부를 같이 while 반복문에서 풀어나간 점

그래서 while 문 안에 if, else 조건식도 많아지고 복잡해졌다. 생각해 본 해결 방법은 아래와 같다.

괄호 완전성 여부 검사와 괄호 회전을 분리해서 구현을 하는 것이다.

def solution(s):
    answer = 0
    
    def ch(s):
        stk=[]
        i,l=0,len(s)
        
        while i<l:
            if s[i]=='(' or s[i]=='[' or s[i]=='{':
                stk.append(s[i])
            elif len(stk)>0:
                if (s[i]=='}' and stk[-1]=='{') or (s[i]==']' and stk[-1]=='[') or (s[i]==')' and stk[-1]=='(') :
                    stk.pop()
                else:
                    return False
            else:
                 return False
            i+=1
        if len(stk)>0:
            return False
        else: return True
            
    for i in range(len(s)):
        front=s[0:i]
        temp= s[i:]+front
        if ch(temp): answer+=1
        
    return answer

 

이렇게 구현을 하게 되면 단순히 괄호 회전을 진행하면서 괄호 완전성을 그때 그때 함수로 판단할 수 있기 때문에 훨씬 단순해졌다. 시간 복잡도는 O(n²)으로 해결할 수 있다.