[문제풀이] 괄호 회전하기

Об этом предложении

문제 괄호 회전하기 문제 설명 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. () , [] , {} 는 모두 올바른 괄호 문자열입니다. 만약 A 가 올바른 괄호 문자열이라면, (A) , [A] , {A} 도 올바른 괄호 문자열입니다. 예를 들어 [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s 가 매개변수로 주어집니다. 이 s 를 왼쪽으로 $x()$ 칸 만큼 회전시켰을 때 s 가 올바른 괄호 문자열이 되게 하는 x 의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 s 의 길이는 1 이상 1,000 이하입니다. 입출력 예시 s result " {}" 3 "}]()[{" 2 "[)(]" 0 "}}}" 0 문제 풀이 " {}" 0 1 2 3 4 5 [ ] ( ) { } 6바퀴를 돌려야 함. (0 ~ 5) 1 2 3 4 5 0 ] ( ) { } [ i만큼 반복하고 j가 인덱스가 되어야 함. i + j i가 0일 때, 0, 1, 2, 3, 4, 5 i가 1일 때, 1, 2, 3, 4, 5, 6 (6 % 6 = 0) i가 2일 때, 2, 3, 4, 5, 6(6 % 6 = 0), 7(7 % 6 = 1) ... i가 5일 때, 5, 6(6 % 6 = 0), 7(7 % 6 = 1), 8(8 % 6 = 2), 9(9 % 6 = 3), 10(10 % 6 = 4) 초기 문제 풀이는 다음과 같이 했다. def solution(s): if len(s) == 1: return 0 answer = 0 length = len(s) for i in range(length): pairs = [0] * 3 for j in range(length): index = (i + j) % length if s[index] == '(': pairs[0] += 1 elif s[index] == ')': pairs[0] -= 1 elif s[index] == '{': pairs[1] += 1 elif s[index] == '}': pairs[1] -= 1 elif s[index] == '[': pairs[2] += 1 elif s[index] == ']': pairs[2] -= 1 if pairs[0] < 0 or pairs[1] < 0 or pairs[2] < 0: break if pairs[0] == 0 and pairs[1] == 0 and pairs[2] == 0: answer += 1 return answer 그러나 틀렸다. 왜 틀렸나 문제를 다시 보니 올바른 괄호는 열리고 바로 닫혀야 하는 것이다. {(}) 이런 거는 올바른 괄호로 보지 않는데 현재 로직에서는 올바른 괄호로 보고 있다. 스택을 활용해서 쌓고 빼고를 해야 할 것 같다. 그리고 {() 와 같은 홀수는 항상 짝이 맞지 않아 아무리 돌려도 올바르지 않은 괄호이다. 따라서 홀수이면 0을 조기 반환한다. if len(s) % 2 != 0: return 0 괄호들의 짝을 딕셔너리로 관리하여 스택에 넣고 빼도록 했다. pairs = {')': '(', '}': '{', ']': '['} 따라서 최종적으로 문제 풀이는 다음과 같다. def solution(s): # 홀수는 항상 올바르지 않는 괄호를 반환하므로 조기 반환 if len(s) % 2 != 0: return 0 answer = 0 length = len(s) # 괄호들의 짝 관리 딕셔너리 pairs = {')': '(', '}': '{', ']': '['} # 회전하기 위한 for 문 for i in range(length): stack = [] is_valid = True # 올바른 괄호인지를 확인하는 for문 for j in range(length): # 인덱스가 넘어가지 않도록 조정 char = s[(i + j) % length] # 여는 괄호라면 stack에 추가 if char in "({[": stack.append(char) # 닫는 괄호라면 else: # 만약 stack이 비어있거나 내 짝이 아닌 괄호라면 올바르지 않은 괄호이므로 for문 빠져나가기 if not stack or stack[-1] != pairs[char]: is_valid = False break # 위 if문을 통과했다면 올바른 괄호이므로 pop 수행 stack.pop() # 올바른 괄호 for문을 빠져 나와 올바른 괄호이면 결과 값에 +1 해주기 if is_valid and not stack: answer += 1 return answer 위 풀이를 리팩터링 해본 풀이 def is_valid(s): stack = [] pairs = {')': '(', '}': '{', ']': '['} for char in s: if char in '({[': stack.append(char) else: if not stack or stack[-1] != pairs[char]: return False stack.pop() return len(stack) == 0 def solution(s): if len(s) % 2 != 0: return 0 answer = 0 for i in range(len(s)): if is_valid(s[i:] + s[:i]): answer += 1 return answer 느낀점 우선 문제를 제대로, 잘 읽고 이해하는 것이 중요하다고 생각했다. 이전에 올바른 괄호 문제에 회전시키면 다라고 생각했는데 그게 아니었던 것이었다. 조기 반환의 경우도 2개씩 짝이 되는 것을 보고 짝수만 올바른 괄호가 되는구나라는 생각을 했어야 하는데 "하나면 안되네?" 라는 생각만 했다. 큰 차이는 아닐지 모르겠으나 메모리, 시간을 절약할 수 있는 조기 반환을 위해 조건을 생각해보는 연습을 해야겠다. 슬라이싱에 대해서도 좀 더 배운 것 같다. 문자열을 회전시킬 때는 항상 % 연산으로만 했었는데 슬라이싱이라는 것이 있다는 것을 보고 놀랐다. 앞으로는 자주 써먹지 않을까 싶다.