[프로그래머스][level2] 괄호 회전하기-python

문제 설명

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

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

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

---

제한사항

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

---

입출력 예sresult

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

---

입출력 예 설명

입출력 예 #1

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

xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?

0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

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

입출력 예 #2

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

xs를 왼쪽으로 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 해야 합니다.

---

※ 공지 - 2021년 4월 16일 테스트케이스가 추가되었습니다.

 

문제 링크

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

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

 

풀이

큐를 사용하여 풀이

큐의 왼쪽에서부터 하나씩 뺀 후 만약 (, {, [ 이면 count +1  아니면  count -1

만약 count가 음수가 되면 잘못된 괄호이므로, Fasle 리턴 

from collections import deque
def solution(s):
    answer = 0
    queue = deque(s)
    for _ in range(len(s)):
        result = check(queue)
        if result :
            answer +=1
        tmp = queue.popleft()
        queue.append(tmp)
        
    return answer

def check(s):
    count = 0 
    for i in s:
        if i == '[' or i =='{' or i =='(':
            count += 1 
        else : count -= 1
        if count < 0:
            return False
        
    return True

그러나, 이렇게  풀면 

"[)(]" 이런 경우를 잘못됐다고 판단하지 못함 

따라서 아래와 같이 수정 

from collections import deque
def solution(s):
    answer = 0
    queue = deque(s)
    # 회전시켜서 check 
    for _ in range(len(s)):
        result = check(queue)
        if result :
            answer +=1
        tmp = queue.popleft()
        queue.append(tmp)
        
    return answer

def check(s):
    count = 0 
    stack = []
    for i in s:
        if i == '[' or i =='{' or i =='(':
            stack.append(i)
        else:
            if not stack:
                return False
            x = stack.pop()
            if i ==')' and x != '(':
                return False 
            if i =='}' and x != '{':
                return False 
            if i ==']' and x != '[':
                return False 
    # stack 에 남아있을 수 있음 
    if not stack :
        return True
    return False

회전 시키는 부분 rotate 함수 사용해서 간단하게 표현 가능 

def solution(s):
    answer = 0
    queue = deque(s)
    for _ in range(len(s)):
        if check(queue) :
            answer +=1
          # 왼쪽으로 한칸 shift
        queue.rotate(-1)
        
    return answer