[알고리즘] 괄호 변환

sith-call.dev·2023년 7월 8일

Cache DP recursiondepth traceback.print_exe 구현 카카오 프로그래머스

알고리즘

목록 보기

31/47

문제

코드

import sys
import traceback
sys.setrecursionlimit(10**8)

valid_cache = dict()
split_cache = dict()

# 올바른 괄호 문자열인지 판단 함수
def is_valid(p):
    global valid_cache
    if p in valid_cache.keys():
        return valid_cache[p]
    stack = []
    for cell in p:
        if cell == "(":
            stack.append(cell)
        elif cell == ")":
            if stack:
                stack.pop()
            else:
                return False
    if stack:
        valid_cache[p] = False
        return False
    else:
        valid_cache[p] = True
        return True
    

# 더 이상 분리할 수 없는 균형잡힌 괄호 문자열 파싱 함수
# 최초로 분리 되는 균형잡힌 괄호 문자열(u) + 나머지(v)
def split_bucket(p):
    global split_cache
    if p in split_cache.keys():
        return split_cache[p]
    left_cnt = 0
    right_cnt = 0
    idx = -1
    for i, cell in enumerate(p):
        if i == len(p) - 1:
            return (p, "")
        elif left_cnt != 0 and left_cnt == right_cnt:
            idx = i
            break
        elif cell == "(":
            left_cnt += 1
        elif cell == ")":
            right_cnt += 1
    u = p[:idx]
    v = p[idx:]
    split_cache[p] = (u, v)
    return (u, v)


def reverse_bucket(p):
    lst = []
    for cell in p:
        if cell == "(":
            lst.append(")")
        elif cell == ")":
            lst.append("(")
    return ''.join(lst)
    

def convertor(p):
    # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
    if not p:
        return ""
    
    # 2 단계
    u, v = split_bucket(p)
    if is_valid(u):
        p2 = convertor(v)
        return ''.join([u, p2])
    else:
        lst = ["("]
        p2 = convertor(v)
        lst.extend(list(p2))
        lst.append(")")
        u_length = len(u)
        if u_length >= 3:
            lst.extend(list(reverse_bucket(u[1:u_length-1])))
        else:
            lst.append("")
        return ''.join(lst)
    
    
def solution(p):
    try:
        return convertor(p) 
        # print(split_bucket(""))
    except:
        # printing stack trace
        traceback.print_exc()

느낀 점

역시 구현 문제는 문제 분석이 최우선! (feat. 카카오)

해당 문제는 얼핏 보면 어려워 보인다.
그러나 구현 문제, 특히 카카오 구현 문제는 문제 자체의 조건이 어렵지 코딩이 어려운 유형은 아니다.
그렇기 때문에 문제를 처음 본 순간부터 차분하게 문제에서 하란 대로 하는게 제일 중요하다.
난 뇌를 빼고 문제에서 적힌대로 구현했더니 아주 손쉽게 문제를 풀 수 있어서 내가 유형화 시킨 대로 카카오 유형이 풀려서 뿌듯했다.

recursion depth limit을 대하는 자세

sys.setrecursionlimit(10**8)

import sys
sys.setrecursionlimit(10**8)

code ...

위와 같은 설정을 통해서 recursion depth limit으로 인한 오류를 해결할 수도 있다. 그러나 문제를 잘 출제하는지 이런 시스템 설정을 변경해서 문제가 풀린 경우는 딱 한번뿐이었다. 어떤 문제였는지는 기억이 안나지만 아무리 봐도 코드의 문제가 없었기 때문에 한번 시스템 설정을 통해 recursion depth를 수정해보니 문제가 통과됐던 경험이 있다.

DP(Cache)를 이용..?

cache = dict()

def function(data):
	if data in cache.keys():
    	return cache[data]
    ....
    result = inner_logic()
    cache[data] = result
    return result

재귀함수를 쓰는 경우에 DP를 cache처럼 구현한다. 그리고 만약 cache에 있는 데이터에 대한 함수가 호출되는 경우 캐시가 hit되어서 해당 스택 프레임이 곧바로 값을 반환하도록 한다. 그리고 파이썬의 dictionary는 key를 통해 값을 불러오는 시간 복잡도가 O(1)이기 때문에 cache로 쓰기 매우 적합하다.
그러나 신기하게도 프로그래머스의 문제에서는 캐시를 쓰든 말든 아무런 상관 없도록 문제가 출제되었다. 오히려 캐시를 쓰니 실행속도가 줄어드는? 진귀한 현상을 관찰할 수 있었다. 이것은 따로 정리하도록 하겠다.

traceback.print_exc() 사용

import traceback

def solution(p):
    try:
    	result = inner_logic()
        return result
    except:
        # printing stack trace
        traceback.print_exc()