[Programmars] Lv.2 괄호 회전하기 - 파이썬

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

 

[문제 설명]

 

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

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

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

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 해야 합니다.

 

 

[문제 풀이]

 

스택을 배울때 대표 예제로 쓰이다 싶이 하는 괄호검사를 응용한 문제입니다.

코드는 아래와 같고 괄호검사하는 check 함수와 rotate한 배열로 check함수 호출하는 부분 이렇게 두가지로 나뉩니다.

괄호검사하는 부분은 간단합니다. 스택의 LIFO성질을 이용합니다.

 

괄호 검사

1. 각 괄호의 짝꿍을 적은 딕셔너리를 생성합니다.

2. 리스트[0]부터 차례대로 돌면서 {, (, [가 나오면 스택에 push

3. }, ), ]가 나오면 pop해와서 짝이 맞는지 확인합니다. 이때 pop해올게 없는 경우(왼쪽과 오른쪽 괄호중에 오른쪽만 남아있는 불균형한 상태)도 체크해줍니다.

 

Rotate

리스트 회전은 collections의 dequq.rotate()메소드를 활용할수도 있지만 코드적으로 구현하는것도 간단하기 때문에 코드로 구현해봤습니다.

"[ ]( ){ }" 파란색+핑크색순으로 문자열을 이으면 회전한게 됩니다. 이때 핑크와 파랑의 경계를 i라 하겠습니다.

"[](){}"

"[](){}"

"[](){}"

"[](){}"

    ...

그럼 s[i:]+s[:i]와 같이 표현할 수 있습니다.

match = {']':'[', ')':'(', '}':'{'}

def check(temp):
    arr = []
    for s in temp:
        if s == '(' or s == '{' or s == '[':
           arr.append(s)
        elif s == ')' or s == '}' or s == ']':
            if not arr or arr[-1] != match[s]: #왼쪽과 오른쪽 괄호중에 오른쪽만 남아있는 불균형한 상태
                return 0
            arr.pop()
    if arr:  #왼쪽과 오른쪽 괄호중에 왼쪽만 남아있는 불균형한 상태
        return 0
 
    return 1
    
def solution(s):
    answer = 0
    temp=""
    for i in range(len(s)):
        temp = list(s[i:]+s[:i])
        answer+= check(temp)
    return answer