99클럽 코테 스터디 28일차 TIL : 시뮬레이션

박지원·2024년 8월 19일

99클럽 알고리즘

99클럽 코테 스터디

목록 보기

24/25

오늘의 학습 키워드

스택/큐

공부한 내용 본인의 언어로 정리하기

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

from collections import deque

def solution(s):
    pairs = {']': '[', '}': '{', ')': '('}
    answer = 0  
    
    for i in range(len(s)):
        new_s = deque(s)
        new_s.rotate(-i)
        stack = []
        
        for j in new_s:
            if j in ')]}': 
                if stack and (stack[-1] == pairs[j]):
                    stack.pop() 
                    continue  
                else: 
                    break
                    
            stack.append(j)
        else:
            if not stack:
                answer += 1
                
    return answer

그 길이만큼 rotate 할 수 있는 것이기 문에 i 만큼 rotat 되도록 넣어주었다
그리고 그렇게 rotate 된 문자열을 하나씩 가져와서
닫힌 괄호 - stack 비어있는지 확인, 비어있지 않으면 마지막 요소와 딕셔너리의 짝이 같은지 확인 - stack pop 하여 요소를 제거
만약에 닫힌 괄호가 아니라면 - append
for 루프가 정상적으로 완료되었을 때 - 이때, stack이 비어 있으면 (not stack), 괄호가 모두 짝을 이루었다는 뜻이므로 answer를 증가

회고

rotate 는 구글링을 통해 함수를 찾음
덱을 이용하는 것은 알았지만, 구체적인 구현을 설계하지 못함
특히 문자열을 고려하는게 어려웠음

다른 풀이 방법


def is_valid(s):
    stack = []
    for ch in s:
        if not stack:
            stack.append(ch)
        elif stack[-1] == '(':
            if ch==')': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '{':
            if ch=='}': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '[':
            if ch==']': stack.pop()
            else: stack.append(ch)

    return False if stack else True

def solution(s):
    answer = 0
    for i in range(len(s)):
        answer += is_valid(s[i:]+s[:i])
    return answer