/ ALGORITHM

(프로그래머스 with python) 괄호변환


Level2 - 괄호변환

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

어려웠다.. 재귀를 이용해야 했지만 어떻게 활용해야 할지 감이 안왔다. 다른 풀이를 보고 이해는데 목표를 둔 문제였다.


# step1 u,v분리하기
def divUV(p):                                                
    left, right = 0, 0
    for i in range(len(p)):
        if p[i] == '(':
            left += 1
        else:
            right += 1
        if left == right:
            u = p[:i+1]
            v = p[i+1:] if i + 1 < len(p) else "" # v = p[i+1: ] 로만 하면 out of index 오류가 발생할 수 있다.
            break
    return u, v


# step2 올바른 괄호 문자열 판별하기
def isCorrect(p):
    stack = []
    for c in p:
        if c == '(':
            stack.append(c)
        else:
            if not len(stack):
                return False
            elif stack[-1] == '(':
                stack.pop()
    return False if len(stack) else True


def rec(p):
    result = ''
    if not len(p): 
        return ''
    u, v = divUV(p)
    if isCorrect(u):
        result = u + rec(v)
    else:
        tmp = '('
        tmp += rec(v)
        tmp += ')'
        u = u[1:-1]
        for c in u:
            if c == '(':
                tmp += ')'
            else:
                tmp += '('
        result += tmp
    return result


def solution(p):
    answer = ''
    if isCorrect(p):
        return p
    
    answer = rec(p)
    return answer

solution("()))((()")

위와 같이 지문 순서대로 함수를 만들어 풀 수도 있었지만 lambda함수를 이용해서 간단하게 풀 수 도 있었다(이걸..?)

def solution(p):
    if p=='': 
        return p
    r=True
    c=0
    for i in range(len(p)):
        if p[i]=='(': c-=1
        else: c+=1
        if c>0: r=False
        if c==0:
            if r:
                return p[:i+1]+solution(p[i+1:])
            else:
                return '('+solution(p[i+1:])+')'+''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) ))

solution("()))((()")