Level 2. 괄호 회전하기

괄호 회전하기

코딩테스트 연습 > 월간 코드 챌린지 시즌2 > 괄호 회전하기

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

문제 설명

# 문제 정리

- 입력: 대,중,소괄호로 구성된 문자열
- 과정:
  1. 매칭되는 괄호를 dict 형태로 생성
  2. s[i:]+s[:i] for i in range(len(s))를 이용하여 i만큼 shift한 문자열 생성
  3. 생성된 문자열을 가장 앞 원소부터 탐색하기 위해 빈 array 생성
    ㄱ. array == [] 일 경우 생성된 문자열의 가장 앞 원소를 append()
    ㄴ. 아닐 경우
      1) array 에 가장 최근 append 된 원소가 ],},) 일 경우, 해당 문자열은 올바르지 않은 문자열이기에 False
      2) 문자열의 원소가 array에 최근 append 된 값과 dict에서 매칭될 때, array의 해당 값을 pop()함으로써 빈 array에 대한 방향성을 가지게 함
      3) 2)에 해당하지 않을 경우, array에 해당 원소를 append
  4. 위 과정을 거친 후, array가 빈 경우, 참이기에 answer+=1
  5. return answer

문제 풀이

# Inpput value
s = "[](){}"
answer = 0 # Set initial value
#01 Set correct bracket
correct= {'{':'}','(':')','[':']'} 
#02 Make rotate s array
from collections import deque
for i in range(len(s)):
    rotate = deque(s[i:]+s[:i]) # Rotate array
    compare= [] # Set blank array to find correct bracket
    while rotate: # Before rotate str is empty
        now = rotate.popleft() # Consider element of rotate str
        if not compare: # If compare array is empty, append(element)
            compare.append(now)
        else:
            if compare[-1] in correct.values(): # If latest appended element in correct.values()
                break # False
            if correct[compare[-1]] == now: # If latest appended element can bind with now,
                compare.pop() # True: Set compare array empty
            else:
                compare.append(now)
    if not compare:
        answer += 1 # Count correct bracket str
answer

괄호의 매칭을 if 로 하나하나 지정하는 방법을 구상하다 dict(key:value)를 이용한 방법을 알게되어 사용해 봤습니다. 또한, 연산속도를 고려하여 deque를 사용하였습니다.

전체 코드

from collections import deque

def solution(s):
    answer = 0

    pare = {'{':'}','(':')','[':']'}
    for i in range(len(s)):
        rotate = deque(s[i:]+s[:i])
        local = []
        while rotate:
            now = rotate.popleft()
            if local == []:
                local.append(now)
            else:
                if local[-1] in pare.values():
                    break
                if pare[local[-1]] == now:
                    local.pop()
                else:
                    local.append(now)
        if local == []:
            answer += 1
    return answer