Programmers / 괄호 회전하기 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 괄호 회전하기 (2단계)

문제 사이트: 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 이하입니다.

---

입출력 예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 해야 합니다.

---

나의 풀이 (첫번째 풀이 14번만 오답, 92.9)

 

예전에 풀었던 올바른 괄호 문제를 떠올리며 풀었다.

def check(arr): 
    # 올바른 괄호인지 확인함
    stack = [] # '()'
    stack2 = [] # '{}'
    stack3 = [] # '[]'

    if arr[0] == '(' : # 첫 괄호가 올바른 방향이면 스택에 쌓는다.
        stack.append(arr[0])
    elif arr[0] == '{':
        stack2.append(arr[0])
    elif arr[0] == '[':
        stack3.append(arr[0])
    else: # 첫 괄호가 올바른 방향이 아니면 아니면 올바르지 않은 괄호로 False를 출력
        answer = False 
        return answer

    for i in range(1,len(arr)):
        if arr[i] == '(': 
            stack.append(arr[i]) #'('는 스택에 쌓는다
        elif arr[i] == ')': #만약 ')' 괄호라면 
            if stack == []: #스택이 비어있으면 쌓는다
                stack.append(arr[i])
                break # for문을 빠져나간다
            if stack[-1] == '(': #만약 스택에 마지막괄호가 '('라면
                stack.pop() # 스택의 마지막 괄호'(' 를 pop해준다. (올바른 괄호이므로)
                
        if arr[i] == '{': 
            stack2.append(arr[i]) #'{'는 스택에 쌓는다
        elif arr[i] == '}': #만약 '}' 괄호라면 
            if stack2 == []: #스택이 비어있으면 쌓는다
                stack2.append(arr[i])
                break # for문을 빠져나간다
            if stack2[-1] == '{': #만약 스택에 마지막괄호가 '{'라면
                stack2.pop() # 스택의 마지막 괄호'{' 를 pop해준다. (올바른 괄호이므로)
                
        if arr[i] == '[': 
            stack3.append(arr[i]) #'['는 스택에 쌓는다
        elif arr[i] == ']': #만약 ']' 괄호라면 
            if stack3 == []: #스택이 비어있으면 쌓는다
                stack3.append(arr[i])
                break # for문을 빠져나간다
            if stack3[-1] == '[': #만약 스택에 마지막괄호가 '['라면
                stack3.pop() # 스택의 마지막 괄호'[' 를 pop해준다. (올바른 괄호이므로)

    if stack == [] and stack2 == [] and stack3 == []: #스택이 모두 비어있으면 True
        answer = True
    else: # 스택이 비어있지 않으면 False
        answer = False
    return answer

def solution(s):
    cnt = 0
    s = list(s)
    l = len(s)
    for i in range(l):
        #리스트 회전
        s.append(s.pop(0))
        if check(s):
            cnt += 1
        
    return cnt

내가 짠 코드는 '([{)}] ' 이 케이스를 고려 못한다. (왜냐면 스택을 모두 분리해서 확인하면 올바른 괄호이므로)

그래서 스택을 그냥 하나로 통일했다.

이게 더 확실한 답인듯

 

나의 풀이 2

def check(arr): 
    # 올바른 괄호인지 확인함
    stack = [] 

    if arr[0] == '(' : # 첫 괄호가 올바른 방향이면 스택에 쌓는다.
        stack.append(arr[0])
    elif arr[0] == '{':
        stack.append(arr[0])
    elif arr[0] == '[':
        stack.append(arr[0])
    else: # 첫 괄호가 올바른 방향이 아니면 아니면 올바르지 않은 괄호로 False를 출력
        answer = False 
        return answer

    for i in range(1,len(arr)):
        if arr[i] == '(': 
            stack.append(arr[i]) #'('는 스택에 쌓는다
        elif arr[i] == ')': #만약 ')' 괄호라면 
            if stack == []: #스택이 비어있으면 쌓는다
                stack.append(arr[i])
                break # for문을 빠져나간다
            if stack[-1] == '(': #만약 스택에 마지막괄호가 '('라면
                stack.pop() # 스택의 마지막 괄호'(' 를 pop해준다. (올바른 괄호이므로)
                
        if arr[i] == '{': 
            stack.append(arr[i]) #'{'는 스택에 쌓는다
        elif arr[i] == '}': #만약 '}' 괄호라면 
            if stack == []: #스택이 비어있으면 쌓는다
                stack.append(arr[i])
                break # for문을 빠져나간다
            if stack[-1] == '{': #만약 스택에 마지막괄호가 '{'라면
                stack.pop() # 스택의 마지막 괄호'{' 를 pop해준다. (올바른 괄호이므로)
                
        if arr[i] == '[': 
            stack.append(arr[i]) #'['는 스택에 쌓는다
        elif arr[i] == ']': #만약 ']' 괄호라면 
            if stack == []: #스택이 비어있으면 쌓는다
                stack.append(arr[i])
                break # for문을 빠져나간다
            if stack[-1] == '[': #만약 스택에 마지막괄호가 '['라면
                stack.pop() # 스택의 마지막 괄호'[' 를 pop해준다. (올바른 괄호이므로)

    if stack == [] : #스택이 모두 비어있으면 True
        answer = True
    else: # 스택이 비어있지 않으면 False
        answer = False
    return answer

def solution(s):
    cnt = 0
    s = list(s)
    l = len(s)
    for i in range(l):
        #리스트 회전
        s.append(s.pop(0))
        if check(s):
            cnt += 1
        
    return cnt

 

---

※ 알아야 할 것

- 다른 괄호 문제 참고

https://sillon-coding.tistory.com/115

백준 / 9012번 괄호 / Python 파이썬

https://sillon-coding.tistory.com/114?category=1013387 

Programmers / 올바른 괄호 / Python 파이썬