🤖 옌지니어의 IT 기록 🤖

https://school.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이하입니다.

입출력 예

소스 코드

def solution(s):
    answer = 0
    n = len(s)

    for i in range(n):
        stack = []  
        for j in range(n):
            # 문자열 회전
            c = s[(i+j)%n]

            # 열린괄호의 경우
            if c=="(" or c=="[" or c=="{":
                stack.append(c)
            # 닫힌괄호의 경우
            else:
                # 스택이 비어있다면 0을 추가하고 종료
                if len(stack)==0:
                    stack.append(0)
                    break
                # 스택의 가장 마지막을 확인하고 짝이 맞다면 제거
                elif c==")" and stack[-1]=="(":     
                    stack.pop()
                elif c=="]" and stack[-1]=="[":
                    stack.pop()
                elif c=="}" and stack[-1]=="{":
                    stack.pop()
                # 짝이 맞지 않은 경우 0을 추가하고 종료
                else:
                    stack.append(0)
                    break
        
        # 중간에 종료되지 않았다면 스택은 비어있으므로 +1
        if not stack:
            answer += 1

    return answer

풀이

• for문에 따라 괄호 문자열을 회전
• 문자열이 열린괄호인 경우 스택에 괄호를 추가
• 문자열이 닫힌괄호인 경우
  • 닫힌괄호이면서 스택이 비어있다면 앞에 열린괄호가 없는 것이므로 스택에 0을 추가하고 종료
  • 닫힌괄호와 스택에 마지막 문자와 짝 맞추기 (짝이 맞다면 제거)
  • 짝이 맞지 않다면 스택에 0을 추가하고 종료
• 중간에 종료되었다면 스택에 0이 있을 것이고 아니라면 스택이 비어있을 것이므로 answer + 1

문자열을 회전하면서 짝을 맞춰야하는 문제였다. 경우의 수를 나누어서 생각하는 것이 좀 어려웠다... 알고리즘 책에서 스택의 예시 문제로 나와있어서 스택으로 풀어야겠다고 생각할 수 있었는데 문제만 봤을 때는 스택을 떠올리기 힘들었을 것 같다.