Programmers_괄호 회전하기

[월간 코드 챌린지 시즌2] 괄호 회전하기

link: 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

입출력 예 설명

• 입출력 예 #1
  다음 표는 "{}" 를 회전시킨 모습을 나타낸 것입니다.
  x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

  • "{}" O
  • "](){}[" X
  • "(){}[]" O
  • "){}[](" X
  • "{}" O
  • "}{" X
    올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

• 입출력 예 #2
  다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
  x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

  • "}]()[{" X
  • "]()[{}" X
  • "()[{}]" O
  • ")[{}](" X
  • "{}" O
  • "{}]()[" X
    올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

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

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

Cdoe 접근

로테이트를 할때마다 올바른 괄호문자열인지 확인할 수 있는 함수를 만든다.
올바른 괄호 문자열인지 확인하는 함수는 다음을 생각하면 쉽게 접근할 수 있다.
1. 좌괄호는 리스트에 넣어준다.
2. 우괄호는 리스트가 비어있다면 올바르지 않기 때문에 바로 return 해준다.
3-1. 만약 리스트안에 좌괄호가 있다면 짝이 맞는지 확인하고 짝이 맞으면 기존 리스트 안에 있는 좌괄호를 삭제해준다.
3-2. 만약 리스트 안에 우괄호가 있다면 이 또한 올바르지 않기 때문에 바로 return을 해준다.

Code | Python

def check(s_list):
	temp = []
	left = ["(","[","{",]
	for x in s_list:
		# print(x,"___",temp)
		if x in left:
			temp.append(x)
		else:
			if not temp: return 0
			if temp[-1] in left:
				if temp[-1] == "(" and x==")": temp.pop()
				elif temp[-1] == "[" and x=="]": temp.pop()
				elif temp[-1] == "{" and x=="}": temp.pop()
				else: temp.append(x)
			else: return 0
	if not temp: return 1
	return 0

from collections import deque
def solution(s):
	answer = 0
	queue = deque(s)
	for i in range(len(s)):
		answer += check(queue)
		queue.append(queue[0])
		queue.popleft()

	return answer

Code Screen Shot | Input & Output

#1
Input: solution("{}")
Output: 3

#2
Input: solution("}]()[{")
Output: 2