[프로그래머스] Lv2 - 괄호 회전하기 (파이썬)

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

코딩테스트 연습 - 괄호 회전하기

 

def solution(s):
    answer = 0
    for k in range(len(s)):
        temp = s[k:]+s[:k]
        if check(temp):
            answer += 1
    return answer


def check(temp):
    arr = list(temp)
    if arr[0] in (')', '}', ']'):
        return False
    if arr[-1] in ('(', '{', '['):
        return False
	# 스택 이용
    dict = {')': '(', '}': '{', ']': '['}
    stack = []
    for x in arr:
        if not stack:
            stack.append(x)
        elif x in dict.keys() and stack[-1] == dict[x]:
            stack.pop()
        else:
            stack.append(x)
    if stack:
        return False
    return True

 

자료구조, 스택
1. 문자열 s를 0번부터~len(s)-1번까지 회전
2. 1의 결과에 대하여 각각 check : 올바른 괄호인지 확인
    - arr의 시작이 닫히는 괄호이면 return False
    - arr의 끝이 열리는 괄호이면 return False
    - 괄호 쌍을 딕셔너리로 기억
    - stack이 비어있으면 추가
    - x가 닫히는 괄호이고 stack의 마지막이 dict[x]와 같다면 stack.pop()
    - 아니라면 stack.append
    - 스택이 비어있다면 return True 아니라면 return False
3. check의 결과가 True 라면 answer += 1
4. answer 리턴

 

s의 길이가 N이라면 이다. (N은 최대 1000)

회전하는데 N이 걸리고

각각 회전한 결과에 대해서 스택을 이용하여 체크하는데 N이 걸리므로

시간 복잡도 O(N^2)으로 만족한다.

 

괄호 관련된 문제는 스택을 많이 사용한다