[이코테] DFS/BFS_괄호 변환 (python)

문제

나의 풀이

1. 몇몇개 함수로 만들어서: 성공..

def correct_str(x): # 올바른 괄호 문자열인지 확인
    a  = []
    for i in x:
        if i == '(':
            a.append(i)
        else: # i == ')'
            if not a: # a가 비어있다면
                return False # 짝이 안 맞으니까
        	a.pop() # 짝이 맞으면, pop
    return True

def balance_str(x): # 균형잡힌 괄호 문자열인지 확인: u와 v를 가르는 인덱스를 구하자
    left, right = 0, 0
    for i in range(len(x)):
        if x[i] == '(':
            left += 1
        else:
            right += 1
        if left == right:
            return x[:i + 1], x[i + 1:]
        
def stage_4_4(x): # 4-4 단계 함수
    x_4_4 = ''
    for i in x[1:-1]:
        if i == '(':
            x_4_4 += ')'
        else:
            x_4_4 += '('
    return x_4_4

answer = ''
def solution(p):
    global answer
    if not p or correct_str(p): # 1. 빈 문자열이거나 올바른 괄호인 경우, 그대로 반환
        return p
    u, v = balance_str(p) # 2. u, v로 나눔
    if correct_str(u): # 3-1.
        return u + solution(v)
    else: # 4.
        answer +='(' + solution(v) + ')'+ stage_4_4(u)
    return answer

의문점

1. correct_str(x)을 '()'를 빼면서 빈문자열로 만드는 방법으로 하면 시간초과가 난다. Why..?

다른 사람 풀이

1. 정석적인 풀이? (프로그래머스)

# if "균형잡힌 괄호 문자열", then return True
def isBanlancedString(str):
    return str.count('(') == str.count(')')

# if "올바른 괄호 문자열", then return True
def isCorrectString(str):
    count = 0
    for s in str:
        if s == '(':
            count += 1
        else: # ')'
            count -= 1
        if count < 0:
            return False
    return count == 0

def process(str):
    # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if str == "":
        return ""
    # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    u, v = splitUV(str)
    print(u, v)
    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    #   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
    if isCorrectString(u):
        u += process(v)
        return u
    else: # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
    #   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
        newStr = "("
    #   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
        newStr += process(v)
    #   4-3. ')'를 다시 붙입니다.
        newStr += ")"
    #   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
        if len(u) > 0:
            newStr += reverseStr(u[1:-1])
    #   4-5. 생성된 문자열을 반환합니다.
        return newStr

def reverseStr(str):
    ans = ""
    for s in str:
        if s == "(":
            ans += ")"
        else:
            ans += "("
    return ans

# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
def splitUV(str):
    u, v = str, ""
    for i in range(2, len(str), 2):
        if isBanlancedString(str[:i]):
            u = str[:i]
            v = str[i:]
            break
    return u, v

def solution(p):
    p = p.strip()

    if isCorrectString(p): # 이미 올바른 괄호 문자열이라면 그대로 return
        return p

    return process(p)

2. 숏코딩(프로그래머스)

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]) ))

• 올바른 괄호 자체를 파이썬에서는 True라고 인식
• ''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) )) 대신 ''.join(['(' if x==')' else ')' for x in p[1:i]]) 도 가능
• map 또한 iterable이니 list()로 변환하는 과정은 필요 없네요