Programmers, 월간 코드 챌린지 시즌2, 스택, ‘괄호 회전하기’

프로그래머스 월간 코드 챌린지 시즌2 문제 중 76502번 ‘괄호 회전하기’

https://school.programmers.co.kr/learn/courses/30/lessons/76502?language=python3

문제 설명

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 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|

입출력 설명 에

입출력 예 #1

• 다음 표는 “{}” 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	”{}”	O
1	”](){}[”	X
2	”(){}[]”	O
3	”){}[](“	X
4	”{}”	O
5	”}{“	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 “}]()[{“ 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	”}]()[{“	X
1	”]()[{}”	X
2	”()[{}]”	O
3	”)[{}](“	X
4	”{}”	O
5	”{}]()[”	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

---

풀이

올바른 괄호인지 검사하는 is_valid 함수로 구현했고, 괄호가 회전하는 부분은 슬라이싱을 활용해 구현해 주었다.

• is_valid 함수
  1. 문자열을 입력받고, 입력받은 문자열 strings의 처음 시작이 닫힌 괄호거나 마지막 끝이 열린 괄호라면 조기종료를 해준다.
  2. strings를 왼쪽부터 접근하기위해 deque 자료형을 d와 괄호검사를 위한 스택 tmp를 선언한다.
  3. d의 원소를 모두 검사할때까지 반복을 하는데, [’[’, ‘{‘, ‘(‘] 안에 d[0]가 있다면 바로 tmp에 d.popleft를 활용해 추가해준다.
  4. d[0]가 [’[’, ‘{‘, ‘(‘]에 존재하지 않는데, tmp가 비어 있다면 유효한 괄호가 아니므로 return False로 검사를 종료한다.
  5. d[0]가 [’[’, ‘{‘, ‘(‘]에 존재하지 않고, tmp가 비어있지 않다면 tmp[-1]와 d[0]로 괄호가 완성되는지 검사하고, 완성되지 않는다면 return False로 검사를 종료한다.
  6. 모든 d를 검사하는 동안 종료되지 않았다면 return True로 검사를 종료한다.
• s[i:] + s[0:i]를 활용해 회전 구현
  1. 슬라이싱 s[i:] + s[0:i]을 통해 회전을 구현 해준다.
  2. (0 ≤ x < (s의 길이)) 모두를 조사야 하므로 for 문을 통해 모든 x에 대해 검사를 진행한다.
  3. is_valid 함수가 True라면 answer을 증가시킨다.

from collections import deque, defaultdict


def solution(s):

    def is_valid(strings):
        print(f'shifted strings: {strings}')
         # 조기 종료 조건
        if strings[0] in [']', '}', ')']:
            return False
        if strings[-1] in ['[', '{', '(']:
            return False

        d = deque(strings)
        tmp = []
        while d:
             # d[0]이 열린 괄호라면 tmp에 넣고 아니라면 다음 조건을 진행
            if d[0] in ['[', '{', '(']:
                tmp.append(d.popleft())

             # d[0]가 닫힌 괄호면서 tmp가 비었다면 조기종료
            elif not tmp:
                return False

             # d[0]와 tmp[-1] 비교를 통해 유효한 괄호인지 검사
            elif d[0] == ']':
                if tmp[-1] == '[':
                    tmp.pop()
                    d.popleft()
                else:
                    return False
            elif d[0] == '}':
                if tmp[-1] == '{':
                    tmp.pop()
                    d.popleft()
                else:
                    return False
            else:
                if tmp[-1] == '(':
                    tmp.pop()
                    d.popleft()
                else:
                    return False

         # 반복이 종료된다면 유효한 괄호이다.
        return True

    n = len(s)
    answer = 0

     # 입력으로 주어진 문자열이 홀수라면 조기종료
    if n % 2 != 0:
        return 0

    for i in range(n - 1):
        if is_valid(s[i:] + s[0:i]):
            answer += 1
    return answer

print(f'answer: {solution("}]()[{")}')

shifted strings: }]()[{
shifted strings: ]()[{}
shifted strings: ()[{}]
shifted strings: )[{}](
shifted strings: [{}]()

answer: 2