[알고리즘] 프로그래머스 Lv2 괄호변환

문제

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

풀이과정

문제를 읽고 이해하는 시간이 조금 필요했던 문제이다.
분할하고 합치는 과정을 보고 merge sort 로직으로 풀고 싶다고 생각했는데 하루가 넘도록 고민해도 merge sort 코드가 생각나지 않았다...
그것은 내가 merge sort를 완전히 이해하고 넘긴게 아니라는 뜻일 것이다.

그래서 "재귀적으로 수행한 결과"를 이어 붙인다는 이 부분을 어떻게 할까 고민을 한참 했는데,
생각해보니 재귀함수는 함수 실행과정이 stack 구조라는 점을 이용하는 것이었다!
그래서 재귀함수가 아니라 stack 구조로 접근했더니 문제를 풀 수 있었다.

1. 균형잡힌 괄호 문자열, 올바른 괄호 문자열을 판단하는 함수를 만든다
2. 주어진 괄호 문자열을 균형잡힌 괄호 문자열 단위로 분해하여 stack에 담는다.
3. (stack은 후입선출) stack 뒤에서부터 2개를 빼서 조건대로 합치고 stack에 다시 추가하는 과정을 stack에 값이 1개만 남을 때까지 반복한다.

코드

# 최소 단위 균형잡힌 괄호 쌍 u, 나머지 v
# v를 계속 쪼개다가 v가 ""이 되면, 합치기
# 합칠 때는, u가 완전한 괄호면 u+v
# u가 균형잡힌 괄호면 (v)+u 앞 뒤 제거 후 괄호 뒤집기
def solution(p):
    def is_right(my_str):
        stack = []
        for s in my_str:
            if s == "(":
                stack.append(s)
            else:
                if stack:
                    stack.pop()
                else:
                    return False
        return True

    def is_balance(my_str):
        if my_str.count("(") == my_str.count(")"):
            return True
        else:
            return False


    stack = []
    start = 0
    end = 1

    while start < end and end <= len(p):
        u = p[start:end]
        v = p[end:]
        if is_balance(u):
            stack.append(u)
            start = end
        end += 1
    stack.append(p[start:end])


    while len(stack) >= 2:
        v = stack.pop()
        u = stack.pop()
        if is_right(u):
            stack.append(u+v)
        else:
            tmp = "(" + v + ")"
            u = u[1:-1]
            while u:
                if u[0] == ")":
                    tmp += "("
                    u = u[1:]
                else:
                    tmp += ")"
                    u = u[1:]
            stack.append(tmp)

    answer = stack.pop()
    return answer


# p = "(()())()"
# p = ")("
p = "()))((()"

print(solution(p))

다른 사람의 풀이

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

프로그래머스에 어떤 천재가 작성한 코드...
r로 올바른 괄호 문자열인지 표시하고
c로 균형잡힌 괄호 문자열인지 표시한 후
재귀적인 방법으로 풀이한 코드이다.
굉장히 간략하지만 가독성도 좋은 코드라고 생각한다.
그저 감탄만... 나도 언젠가...