[Programmers/파이썬] 프로그래머스(Lv.2) 괄호 회전하기 문제풀이

문제 설명

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

프로그래머스

 

 

사고 흐름

1. 이동하는 모든 x에 대해 확인하는 완전 탐색 

2. s를 x만큼 이동 -> 큐 사용하기

3. x만큼 이동한 문자열의 괄호 여부 확인 -> 스택 사용하기

 

문제 핵심과 알고리즘

완전 탐색 + 스택 사용한 올바른 괄호 확인 

def check(s) :
    stack = []
    d = {'(':')', '[':']', '{':'}'}
    
    for e in s :
        if e in d :
            stack.append(e)
        elif stack and d[stack[-1]]==e :
            stack.pop()
        else :
            return False
        
    if stack :
        return False
    else :
        return True

def solution(s):
    answer = 0
    stack = list(s)
    
    for i in range(len(s)) :
        if check(stack) :
            answer+=1
        stack.append(stack.pop(0))
    return answer

 

문자열을 하나씩 이동하면서 check 함수로 올바른 괄호 구조인지 확인한다. 

check 함수는 스택을 사용해서 여는 괄호라면 stack에 추가하고, 닫는 괄호라면 마지막에 연 괄호 먼저 닫아야 하므로 배열 끝에 있는 원소와 비교 후 같으면 pop 하고 아니면 올바른 구조가 아니므로 False를 리턴한다. 그리고 stack에 원소가 남아있다면 그 또한 올바른 구조가 아니므로 false를 리턴한다. (처음에 이 부분을 놓쳐서 tc 하나가 틀렸다)

 

문제 풀면서 헤맸던 부분

딱히 없었다. 

 

총평 

올바른 괄호 판단 문제는 많이 나와서 이제 거의 외웠다. 문자열을 하나씩 미는 방법은 많은데, 나는 큐를 이용했다. (코드에서는 stack 변수를 사용했고, deque를 쓰지는 않았지만, 큐 자료구조를 생각했고 코드에서는 deque로 시간을 단축할 수 있다) 그리고 슬라이스를 통해서도 간단하게 이동할 수 있다.

for i in range(len(s)) :
	if check(s[i:]+s[i:]) :
    		answer+=1