[Python - Lv.2] 괄호 회전하기

문제

프로그래머스

문제

문제

문제 이해

• ( ), [ ], { }는 올바른 괄호 문자열
• A가 올바른 괄호 문자열이면 (A), [A], {A}도 올바른 괄호 문자열 / ex) ( [ ] )
• A, B가 올바른 괄호 문자열이면, AB도 올바른 괄호 문자열 / ex) { }, ( [ ] ) => { } ( [ ] )
• 괄호로 이루어진 문자열 s를 왼쪽으로 x만큼 회전시켰을 때 올바른 괄호 문자열이 되게 하는 x의 개수
• 단, 0 <= x < len(s), 1 <= len(s) <= 1000
• 문자열 s는 입력으로 들어옴

풀이

문자열 s를 0, 1, ..., len(s) -1 만큼 왼쪽으로 회전시키면서 올바른 괄호 문자열인지 판단

1. 올바른 괄호 문자열인지 판단, 올바르면 cnt 증가
2. 왼쪽으로 한 칸씩 회전하며 올바른 괄호 문자열인지 판단
3. 1 ~ 2를 반복

<올바른 괄호 문자열 판단>
1. stack 생성 (list)
2. 문자열 s 순회
    1) 여는 괄호면 무조건 push (append)
    2 - 1) 비어있는데 닫는 괄호면 올바른 괄호 문자열 X
    2 - 2) 안 비어있는데 닫는 괄호이고 top과 짝이 맞으면 pop, 아니면 올바른 괄호 문자열 X
3. 순회 후 stack이 비어있으면 올바른 괄호 문자열 O왼쪽으로 한 칸 회전

<왼쪽으로 한 칸 회전>
(1) 문자열 s를 list로 변경하여 s.append(s[0]), s.pop(0) 활용
=> pop 함수의 시간 복잡도는 O(n)이라서 길이가 길어지면 시간이 오래 걸릴 것이라 예상

(2) 새로운 list를 활용하여 L = s[1:], L.append(0) 및 s = L[:]로 대입
=> 변수를 더 사용하지만, pop 함수를 사용하지 않아 시간이 더 빠를 것이라 예상

코드

확인 결과 실제로 회전 방식을 (2)로 하였을 때, 대체로 더 빠르게 수행하는 모습을 볼 수 있다.

def check_correct(s):
    stack = []
    
    for ch in s:
        if ch == '(' or ch == '{' or ch == '[':
            stack.append(ch)
        else:
            if len(stack) == 0:
                return 0
            else:
                if stack[-1] == '(' and ch == ')':
                    stack.pop(-1)
                elif stack[-1] == '{' and ch == '}':
                    stack.pop(-1)
                elif stack[-1] == '[' and ch == ']':
                    stack.pop(-1)
                else:
                    return 0
    
    if len(stack) != 0:
        return 0
    return 1

        

def solution_1(s):
    # 왼쪽으로 한 칸 회전 (1)
    cnt = 0
    s = list(s)
    for i in range(len(s)):
        s.append(s[0])
        s.pop(0)
        cnt += check_correct(s)
    return cnt
    
def solution_2(s):
    # 왼쪽으로 한 칸 회전 (2)
    cnt = 0
    L = []
    s = list(s)
    for i in range(len(s)):
        L = s[1:]
        L.append(s[0])
        cnt += check_correct(L)
        s = L[:]
    return cnt

왼쪽으로 한 칸 회전 (1)

왼쪽으로 한 칸 회전 (2)