[알고리즘/프로그래머스] - 괄호 변환(python)

문제

과정을 함수로 나누어 코딩을 했습니다.

1. u, v로 나누기

def sep_uv(p):  # 2
    a = 0
    b = 0
    for i in range(len(p)):
        if p[i] == '(':
            a += 1
        else:
            b += 1
        if a == b:
            u = p[:i + 1]
            v = p[i + 1:] if i + 1 < len(p) else ""
            break
    return u, v

왼쪽부터 검사하여 괄호 열림, 닫힘 괄호 갯수가 동일하면 그 부분으로 나눈다.

2. 올바른 괄호 문자열

def correct_check(p):  # 올바른 괄호 문자열 체크
    a = deque(p)
    b = deque()
    flag = True
    for i in range(len(a)):
        if not flag:
            break
        if len(b) == 0:
            if a[0] == '(':
                b.append(a.popleft())
            else:
                flag = False
        else:
            if a[0] == '(':
                b.append(a.popleft())
            else:
                if b[-1] == '(':
                    b.pop()
                    a.popleft()
    if len(b):
        flag = False
    return flag

만약에 큐가 비어있는데 닫는 괄호가 나오면 False
열린 괄호가 큐에 들어있고 닫힌 괄호가 들어오면 pop

3. 나머지 부분

def rec(p):
    res = ""
    if not len(p):  # 1
        return ""
    u, v = sep_uv(p)
    if correct_check(u):  # 3
        res = u + rec(v)
    else:  # 4
        res = '(' + rec(v) + ')'
        u = u[1:-1]
        for i in u:
            if i == '(':
                res += ')'
            else:
                res += '('
    return res

만약 p가 비어있으면 빈 문자열 출력
u, v를 나누고 u를 체크하여 올바른 괄호이면 재귀로 u를 넘겨주기

아니면 ( + rec(v) + )를 실행
u 양 옆을 삭제하고 나머지 뒤집기

전체코드

from collections import deque


def correct_check(p):  # 올바른 괄호 문자열 체크
    a = deque(p)
    b = deque()
    flag = True
    for i in range(len(a)):
        if not flag:
            break
        if len(b) == 0:
            if a[0] == '(':
                b.append(a.popleft())
            else:
                flag = False
        else:
            if a[0] == '(':
                b.append(a.popleft())
            else:
                if b[-1] == '(':
                    b.pop()
                    a.popleft()
    if len(b):
        flag = False
    return flag


def sep_uv(p):  # 2
    a = 0
    b = 0
    for i in range(len(p)):
        if p[i] == '(':
            a += 1
        else:
            b += 1
        if a == b:
            u = p[:i + 1]
            v = p[i + 1:] if i + 1 < len(p) else ""
            break
    return u, v


def rec(p):
    res = ""
    if not len(p):  # 1
        return ""
    u, v = sep_uv(p)
    if correct_check(u):  # 3
        res = u + rec(v)
    else:  # 4
        res = '(' + rec(v) + ')'
        u = u[1:-1]
        for i in u:
            if i == '(':
                res += ')'
            else:
                res += '('
    return res


def solution(p):
    if correct_check(p):
        return p

    answer = rec(p)

    return answer