[Python] 2020 KAKAO BLIND RECRUITMENT : 괄호 변환

2020 KAKAO BLIND RECRUITMENT : 괄호 변환

문제 설명

용어의 정의

매개변수 설명

입출력 예

입출력 예에 대한 설명

문제풀이

처음에는 문제와 그 원리에 대해 이해를 하려고 했는데 잘 안 돼서 못하고 있다가
그저, 용어의 정의에 번호로 나와있는 대로 알고리즘을 만들면 되는 거였다...

1. solution(p)에서 if p == "": return p
2. '('와 ')'의 수가 같을 경우, 문자열을 u, v로 잘라주는 함수를 만든다.
3. u가 올바른 문자열인지 판단하는 함수를 만든다.
   3-1. u가 올바른 문자열일 경우 u + solution(v)
   3-2. u가 올바른 문자열이 아닌 경우, answer = '(' + solution(v) + ')',
   u의 처음과 끝 문자열을 뺀 후, 문자열들을 하나씩 뒤집어준 후 answer 뒤에 붙여준다.
   마지막으로, return answer
   Ex : u = "))(("일 경우 처음과 끝을 자른 ")("만 뒤집어 "()"가 된다.

위의 과정을 거치면 답을 얻을 수 있다.

답

def solution(p):
    ## 빈 문자열일 경우 반환
    if p == "":
        return p

    ## u, v로 분리
    u,v = seperate(p)

    ## 올바른 문자열인지 확인
    if balance(u):
        ## u는 올바른 문자열이니 그대로 넘기고, v는 모르니 solution 로직을 다시 실행
        return u + solution(v)
    else:
        answer = '(' + solution(v) + ')'
        ## u의 처음과 끝을 뺀 후 문자열 하나씩 뒤집기
        for x in u[1:-1]:
            if x == '(':
                answer += ')'
            else:
                answer += '('
        return answer
## u, v로 분리하는 함수
def seperate(p):
    left_count = 0
    right_count = 0

    for i in range(len(p)):
        if p[i] == '(':
            left_count += 1
        else:
            right_count += 1
        ## left_count == right_count일 경우 앞뒤를 나눠 u,v가 된다.
        if left_count == right_count:
            return p[:i+1], p[i+1:]
## 올바른 문자열인지 확인하는 함수
def balance(u):
    stack = []
    for x in u:
        if x == '(':
            stack.append(x)
        else:
            ## '('보다 ')'가 먼저 들어올 경우 잘못된 문자열
            if not stack:
                return False
    else:
        return True