스택 - 괄호 회전하기

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

프로그래머스

 

 

def solution(s):
    answer =0 
    n =len(s)
    for i in range(n):
        stack=[]
        for j in range(n):
            c=s[(i+j)%n]
            if c =="(" or c =="[" or c =="{":
                stack.append(c)
            else:
                if not stack:
                    break
                if c ==")" and stack[-1] =="(":
                    stack.pop()
                elif c =="]" and stack[-1] =="[":
                    stack.pop()
                elif c =="}" and stack[-1] =="{":
                    stack.pop()
                else:
                    break
        else:
            if not stack:
                answer +=1
    return answer

 

........

이문제의 핵심은 닫힌 괄호를 처음 보는 순간 ,

가장 마지막에 찾았던 같은 모양의 열린 괄호를 찾을 수 있어야 한다는 것

 

-> 스택에 적합

 

### 코드 분리해서 설명

def solution(s):
    answer =0 
    n =len(s)
    for i in range(n):
        stack=[]
        for j in range(n):
            c=s[(i+j)%n]

 

문제에서 문자를 왼쪽으로 민다고 했다. -> 맨앞 문자가 맨뒤로 가는 것

인덱스 i를 첫문자라고 하면 j는 다음 문자로 

            c=s[(i+j)%n]

 

위는 회전시킨 배열에서 j번째 값의 위치를 표현하기 위함

 

if c =="(" or c =="[" or c =="{":
                stack.append(c)

 

여는 괄호가 있으면 스택에 푸시 

 

else:
                if not stack:
                    break

 

c는 현재 참조하는 문자이다.

닫는 괄호를 참조할때 스택에 아무 값도 없으면 닫는괄호와 짝을 맞출 여는 괄호가 아예없다는 뜻

검색 중단하고 다음 회전 확인하기 위해 for문 빠져나감

 

if c ==")" and stack[-1] =="(":
                    stack.pop()
                elif c =="]" and stack[-1] =="[":
                    stack.pop()
                elif c =="}" and stack[-1] =="{":
                    stack.pop()
                else:
                    break

 

c가 참조한 닫힌 괄호가 있을때 스택에 여는괄호가 있는경우

최근 여는 괄호, -> 스택의 top 위치 stack[-1]의 괄호와 짝이 맞는지 비교

짝이 맞으면 팝 연산을 수행

 

 else:
            if not stack:
                answer +=1
    return answer

 

파이썬에는 for-else문법이 있다.

else는 for문이 끝까지 실행되었을떄 동작

괄호의 모든 짝이 맞으면 실행

모든 짝이 맞는 문자열마다 answer를 1만큼 증가시킨다.