[프로그래머스] 카카오 2020 blind recruitment - 괄호변환

문제

코딩테스트 연습 - 괄호 변환

 

풀이

구현 자체는 전혀 어렵지 않은 문제다.

다만 스텝바이스텝 정확하게 뭘 하라는건지 설명을 이해하는게 어려웠다 

 

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

 

1단계부터 어디까지 하라는건지 고민했는데 알고보니 전체 solution함수 자체를 돌리라는 말이었다.

 

 

교훈: 문제 이해가 어려우면 테스트케이스 보고 유추 후, 일단 풀기.

실행했을때 틀리면 그때

1. 실수 없는지 먼저 확인 후 2. 의미가 애매했던 부분 설명 다르게 이해해보기

 

def solution(p):
    # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if not p or isTrue(p):
        return p

    # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    u, v = checkBalance(p)

    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    flag = isTrue(u)

    if flag:
        # 문자열 v에 대해 1단계부터 다시 수행합니다.
        # 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
        return u + solution(v)

    else:
        # 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
        str = "(" + solution(v) + ")"
        newu = u[1:-1]
        for each in newu:
            if each == "(":
                str += ")"
            else:
                str += "("

        return str

# 균형잡힌 괄호 문자열인지 확인하는 함수 
def checkBalance(p):
    li = [-1 for _ in range(len(p))]

    index = -1
    for i in range(len(p)):
        if p[i] == "(":
            if i == 0:
                li[i] = 1
            else:
                li[i] = li[i-1] + 1
                if li[i] == 0:
                    index = i
                    break
        else:
            if i == 0:
                li[i] = -1
            else:
                li[i] = li[i-1] - 1
                if li[i] == 0:
                    index = i
                    break

    u = p[:index+1]
    v = p[index+1:]

    return u, v

# 올바른 괄호 문자열인지 체크하는 함수
def isTrue(u):
    stack = []
    for each in u:
        if each == "(":
            stack.append(1)
        else:
            if stack:
                stack.pop()
            else:
                return False
    return True