파이썬 코딩테스트 스터디 3주차 #3 - 괄호 회전하기

 

 

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

 

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다.

이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때

s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

로직1. 왼쪽으로 한칸씩 밀기

 

실제로 한칸씩 밀게되면, 시간 초과가 날 수 있다.

그래서 이 책에서는 마치 왼쪽으로 옮긴 것처럼 하기 위해

오프셋이라는 개념을 두었다.

 

즉 오프셋을 오른쪽으로 한칸씩 옮겨 마치 인덱스안에 값이 왼쪽으로 이동한 것처럼 로직 구현

Index	0	1	2	3	4	5
Value	(	{	[	]	}	)

 

n = 전체 길이 = 6

 

1) 0번만큼 옮겼을 때는 i = 0, j = 0  즉, ( 부터 )까지

    :  (i+j)%n = (0+0)%6 = 0

                   = (0+1)%6 = 1

                   = (0+2)%6 = 2

                   = (0+3)%6 = 3

                   = (0+4)%6 = 4

                   = (0+5)%6 = 5

 

2) 1번만큼 옮겼을 때는 i = 0, j = 1  즉, {부터 (까지

    :  (i+j)%n = (1+0)%6 = 1    → 실제 인덱스 1번을 제일 처음으로 처리

                   = (1+1)%6 = 2

                   = (1+2)%6 = 3

                   = (1+3)%6 = 4

                   = (1+4)%6 = 5

                   = (1+5)%6 = 0   → 실제 인덱스 0번을 마지막으로 처리 

 

 

3) 2번만큼 옮겼을 때는 i = 0, j = 2  즉, [부터 {까지

    :  (i+j)%n = (2+0)%6 = 2    → 실제 인덱스 1번을 제일 처음으로 처리

                   = (2+1)%6 = 3

                   = (2+2)%6 = 4

                   = (2+3)%6 = 5

                   = (2+4)%6 = 0

                   = (2+5)%6 = 1   → 실제 인덱스 0번을 마지막으로 처리 

 

 

... 이런식으로 마지막까지

 

 

로직2. 괄호 짝 맞추기.

1. 만약에 시작 괄호가 열린 괄호면 stack에 추가 

    그렇지 않으면 바로 건너 뛰기

2. 다음께 열린 괄호면 stack에 추가

                닫힌 괄호면 바로 전 stack과 짝이 맞으면 pop하기

3. 이렇게 total = len(s) 길이 만큼 다 돈 경우에만 result+=1

 

 

def solution(s):
    
    answer = 0
    
    total = len(s) #전체 길이 구하기
    
    # 오프셋이라는 개념을 두고 
    # 마치 왼쪽으로 돌리는 효과를 적용.
    
    for i in range(total) : 
        stack=[]
        for j in range(total):
            A = s[(i+j)%total]
            if A =='(' or A =='{' or  A =='[':
                stack.append(A)
            else:
                if not stack:
                    break   #아예 for문을 벗어나 1회전 건너띄기
            
                if A ==')' and stack[-1] =='(':
                    stack.pop()
                elif A =='}' and stack[-1] =='{':
                    stack.pop()
                elif A ==']' and stack[-1] == '[':
                    stack.pop()
                else:
                    break
        else:    #for-else문은 for문이 break를 만나지않고, 다 실행 됬을때만 실행하는 구문
            if not stack:
                answer+=1
    return answer

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스