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

문제 풀이 정리

 

문제 설명

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

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

코드

def isTrueBraket(s): #정규식을 이용해 괄호 등장시 치환하는 함수
    import re
    p = re.compile('\[\w?\]|\{\w?\}|\(\w?\)|AA')
    while True:
        if p.search(s):
            s = re.sub(p,"A",s)
        else:
            break
    
    for braket in s: # 치환결과를 돌면서 사라지지 않은 괄호가 있다면 False
        if braket != 'A':
            return False
    return True


def solution(s):
    answer = 0
    
    for i in range(len(s)):
        if isTrueBraket(s): # 치환후 A만 남으면 answer +1
            answer += 1
        braket = s[0] #왼쪽 맨앞 괄호 가져오기
        s = s[1:] # 맨앞 괄호 제거
        s += braket # 맨뒤 괄호 붙이기
    
    return answer

 

문제 넋두리

 

처음에 stack으로 풀려고 했었다. 잘보니 올바른 괄호는 몇개인가? 였다.

자세히 써보자면 문제에 나와있는것 처럼 문자열의 현재 상태가 {}[()] 경우,

올바른 괄호인가 아닌가를 판별하는 문제인 것이다. 현재 상태에 대한 괄호의 개수가 아니라...

 

그럼 수정해서 특정 괄호패턴이 등장할때 지워 버리면 되지 않을까?

예를 들어보면

{[()]} -> ()을 A 로 치환 -> {[A]} -> [A]를 A로 치환 -> {A} -> A로 치환 -> A

오랜만에 그럴듯한 생각을 '한번에' 할수있다니...

 

함정은 정규 표현식을 내가 잘모른다는 것.

이 기회에 한번 되짚어 보자

wikidocs.net/4308

위키독스

해당 링크를 보고 테스트는

regexr.com/

RegExr: Learn, Build, & Test RegEx

테스트 결과

[] 과 [A] 둘다 감지 할수 있고, 각 괄호에 대해 하나씩 총 3개의 regex 패턴을 만든다.

이걸 코드로 만들어 보자

def isTrueBraket(s): #정규식을 이용해 괄호 등장시 치환하는 함수
    import re
    p = re.compile('\[\w?\]|\{\w?\}|\(\w?\)|AA')
    while True:
        if p.search(s):
            s = re.sub(p,"A",s)
        else:
            break
    
    for braket in s: # 치환결과를 돌면서 사라지지 않은 괄호가 있다면 False
        if braket != 'A':
            return False
    return True

re.compile을 통해 패턴 객체를 만든후

패턴 search 함수를 통해 반복해 돌면서 패턴을 A로 지워준다.

AA의 경우 {AA}의 경우 해당 패턴이 인식하기 못하기 때문에 AA->A로 바꿔주기 위해 추가

(문제 다 풀고 알게 된건데

'\[\w?\]|\{\w?\}|\(\w?\)|AA' 대신

\[\w*\]|\{\w*\}|\(\w*\) 으로 바꿔서

중간에 AA에 대한 예외도 처리하면 된다...)

 

위 판별 함수를 통해 회전된 문자열이 올바른 문자열이 되는지 여부를 판단하니까 잘되었다.

 

역시 파이썬...