알고리즘/프로그래머스

괄호 회전하기 - 파이썬

cafe-jun12 2022. 6. 26. 22:16
반응형

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
  • s의 길이는 1 이상 1,000 이하입니다.

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

 

문제접근 방식 

  • 이문제는 올바른 괄호를 체크하는 문제입니다. 제가 생각하기에는 이 문제를 해결하기 위해서는 두가지 포인드가 있었스빈다.
  • 첫번째로는 자료구조를 이용해서 괄호를 한바퀴 회전할수 있나요 ?
  • 두번째 요구사항은 문제 요구사항에 맞는 올바를 괄호를 체크할수가 있나요 ?
  • 저는 첫번째는 큐를 이용하여 회전을 하였습니다. 첫번째로 넣은걸 마지막에 넣기만 하면 됩니다. 
  • 그다은 올바른 괄호를 체크하는 문제에서는 ({[ 와 ]}) 가 짝이 맞도록 stack을 이용하여 체크를 하였습니다. 
  • 크게 어려운 문제는 아니였습니다만 괄호의 종류가 많아 한번더 생각하는 문제였습니다. 

# 내코드 

from collections import deque

def solution(s):
    answer = 0
    # 올바른 괄호 확인하기
    q = deque(list(s))
    # 회전 카운트
    cycle_cnt = 0
    # 큐를 이용하여 회전을 시켜보자
    while cycle_cnt < len(s):
        # queue 안에 문자열 JOIN 하기
        convert_s = ''.join(q)
        # 올바른 괄호인지 확인
        if correct_check(convert_s):
            # 올바른 괄호라면 카운트 올리기
            answer += 1
        # 괄호 문자열 회전
        q.append(q.popleft())
        # 회전 카운트 올리기
        cycle_cnt += 1
    return answer


def correct_check(s):
    # 체크 초기값 False
    check = False
    # stack 값 초기화
    stack = []
    # 괄호 array
    start_scope = ['(', '{', '[']
    for x in s:
        # stack 아무것도 없다면
        if not stack:
            # {([ 이라면 값 넣기
            if x in start_scope:
                # scope_dic[x] += 1
                stack.append(x)
                continue
            else:
                # 어떻게든 올바르지 못한 괄호
                return False
        # scope_dic에 key 가 있는 값인지 확인
        if x in start_scope:
            # stack 에 값을 넣기
            stack.append(x)
        else:
            # stack pop 하기
            value = stack[-1]
            # 각 괄호 별 체크
            if x == ')' and value == '(':
                stack.pop()
            elif x == ']' and value == '[':
                stack.pop()
            elif x == '}' and value == '{':
                stack.pop()
            else:
                break
    if not stack:
        check = True
    return check

 

 

더 좋은 코드가 있으면 공유 부탁드립니다. 

반응형