[프로그래머스] 괄호 회전하기 - 파이썬

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

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

 

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

 

입출력 예

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

문제 풀이

괄호 짝을 맞추는 문제는 스택을 이용하여 구현하면 해결할 수 있다.

짝을 판단해주는 check 함수를 만들고 문자열을 순서대로 검사하며 여는 괄호( '(' ,'{', '[' )인 경우에 스택에 넣는다.

 

우선 체크함수를 검사하지 않는 조건을 찾아보면 문자열의 길이가 홀수인 경우에는 절대로 짝을 맞출 수 없다.

체크함수를 호출하기 전 입력된 문자열의 길이가 홀수면 바로 리턴한다.

 

체크함수에서 문자열을 검사하며 닫는 괄호가 나온 경우를 생각해보자

1. 스택이 비어 있는 경우 -> 짝을 맞출 수 없음

2. 스택에 괄호가 있는 경우 -> 스택에서 pop 시켜 닫는 괄호와 상응하는 여는 괄호인지 검사

 

1,2 번의 경우를 나눠서 검사하여 문자열의 괄호가 짝을 이룬다면 True를 리턴하고, 짝을 이루지 못하면 False를 리턴.

 

문자열을 왼쪽으로 한 칸씩 미는 코드는 다양한 방법이 있지만 문제를 풀때 바로 생각했던

리스트의 첫 번째 원소 pop -> 다시 리스트의 마지막에 append 방식을 이용했다.

 

def check(li):
    stack = []

    for c in li:
        if c == '(' or c == '{' or c == '[': # 여는 괄호인 경우 스택에 넣음
            stack.append(c)
             
        else:
            if len(stack) == 0:
                return False

            compare_c = stack.pop()

            if c == ']' and compare_c != '[':
                return False

            elif c == ')' and compare_c != '(':
                return False

            elif c == '}' and compare_c != '{':
                return False
                
    return True

def solution(s):
    answer = 0
    if len(s) % 2 == 1:
        return answer
    
    s = list(s)
    
    if check(s):  # 오리지널(원래) 문자 처음으로 검사
        answer += 1
    
    for _ in range(len(s) - 1): # 왼쪽으로 한 칸씩 밀어낸 문자 검사
        word = s.pop(0)
        s.append(word)
        
        if check(s):
            answer += 1
    return answer