[Python] 프로그래머스, 괄호 회전하기 Lv.2 (feat.stack, queue, deque, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

 

 

 

 

 

 

 

괄호 회전하기

문제 링크

프로그래머스

 

 

문제 설명

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

 

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

 

 

 

 

 

 

---

 

 

 

 

 

 

해결 과정

1. 올바른 문자열 확인을 위한 플래그, 반환할 올바른 문자열 카운트 그리고 스택과 큐를 선언해 줍니다.

 

2. 선언한 문자열 큐의 길이만큼 for loop을 돌려 회전해 줍니다.

 

3. 회전된 문자열을 for loop을 돌려 하나씩 확인해 줍니다.

 

4. 괄호를 여는 문자열이면 스택에 저장, 괄호를 닫는 문자열이면 스택의 마지막 값과 확인합니다.

 

5. 스택에 값이 있고 괄호 문자열이 완성되면 제거 후 플래그를 True로 업데이트해 줍니다.

 

6. 올바른 문자열이 만들어졌고 스택이 비어있다면 반환할 카운트를 1씩 증가시켜 줍니다.

 

7. 스택과 플래그를 초기화해 주고 문자열을 회전이 끝날 때까지 3번부터 반복해 줍니다.

 

제출 코드

from collections import deque
def solution(s):
    flag  = False   # 올바른 문자열 확인 플래그
    count = 0      # 올바른 문자열 카운트
    stack = []     # 올바른 문자열 확인을 위한 스택
    queue = deque(s) # 문자열 큐로 변환
    
    # 문자열 큐 길이 만큼 for loop
    for i in range(len(queue)):
        # 괄호 문자열 하나씩 확인하는 for loop
        for el in queue:
            # 괄호 여는 문자열이면 스택에 저장
            if el == '[' or el == '{' or el == '(':
                stack.append(el)
            # 괄호 닫는 문자열이면 스택 마지막 값과 확인
            else:
                # 스택에 값이 있고 괄호 문자열이 완성되면 제거 후 플래그 True
                if stack:
                    if stack[-1] == '[' and el == ']':
                        stack.pop()
                        flag = True
                    elif stack[-1] == '{' and el == '}':
                        stack.pop()
                        flag = True
                    elif stack[-1] == '(' and el == ')':
                        stack.pop()
                        flag = True
        
        # 올바른 문자열이 만들어졌고 스택이 비어있다면 카운트 1씩 증가
        if flag and not stack: count += 1
        
        # 스택, 플래그 초기화, 문자열 회전
        stack = []
        flag = False        
        queue.append(queue.popleft())
        
    # 올바른 문자열 카운트 반환
    return count

 

 

 

 

리팩토링 코드

from collections import deque

def check(s):
    while True:
        if "()" in s: s = s.replace("()","")
        elif "{}" in s: s = s.replace("{}","")
        elif "[]" in s: s = s.replace("[]","")
        else: return False if s else True       

def solution(s):
    count = 0
    queue = deque(s)

    for i in range(len(s)):
        if check(''.join(queue)): count+=1
        queue.rotate(-1)
    return count

 

 

 

 

 

---

 

 

 

 

 

 

또 다른 풀이

def check(s):
        stack = []
        for i in s:
            if len(stack) == 0: stack.append(i)
            else:
                if i == ")" and stack[-1] == "(": stack.pop()
                elif i == "]" and stack[-1] == "[": stack.pop()
                elif i == "}" and stack[-1] == "{": stack.pop()
                else: stack.append(i)
        return 1 if len(stack) == 0 else 0
        
def solution(s):
    count = 0
    
    for i in range(len(s)):
        if check(s): count +=1
        s = s[1:] + s[:1]
    return count

 

 

큐를 사용하지 않고 스택을 활용하여 회전과 확인을 처리한 코드입니다.

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges