2020 KAKAO BLIND RECRUITMENT 괄호변환 파이썬

2020 KAKAO BLIND RECRUITMENT 괄호변환 파이썬 풀이

바로 이전에 풀었던 오픈채팅방 문제와 동일한 2레벨 문제입니다.

약 3시간에 걸쳐 풀었지만 테스트 케이스를 통과하고 제출 후 100점 중 4점밖에 맞지 못했습니다. 결국 다른 사람들의 풀이를 참고하여 코드를 분석해보았습니다. 해당 코드는 이숭간님 블로그 괄호변환 풀이를 참고했음을 밝힙니다.

접근 방식

1. 문제에서 주어진 조건 순서대로 진행합니다.
2. 빈 문자열이 주어질 경우 ““를 return 합니다.
3. 올바른 괄호 문자열과 균형잡힌 괄호 문자열을 분리하기 위한 seperate 함수를 만듭니다.
4. seperate 함수는 각각의 괄호 개수를 누적시키면서 균형을 이루는 순간을 기준으로 합니다.
5. 그리고 해당 문자열이 균형잡힌 문자열인지 확인해주는 함수도 만들어줍니다.
6. solution함수를 실행하여 u, v로 분리해주고, 만약 u가 올바른 괄호 문자열일 경우엔
   v에 대해 다시 수행해주고 앞의 결과를 더해줘야 합니다.
7. 이후 마지막에 주어진 조건에 맞춰 최종 문자열을 만들어줍니다.

def solution(p):
    # 1번
    if not p:
        return ""

    # 2번
    u,v = seperate(p)

    # 3번
    if isBalanced(u):
        #seperate(v)
        # 3-1
        return u + solution(v) # 이부분을 이해하는것이 어려웠다.
    # 4번
    else:
        # 4-1
        answer = '('
        # 4-2
        answer += solution(v)
        # 4-3
        answer += ')'

        # 4-4
        for i in u[1:-1]:
            if i == '(':
                answer += ')'
            else:
                answer += '('
        # 4-5
        return answer

# 문자열을 u와 v로 분리하는 함수
def seperate(p):
    left_count = 0
    right_count = 0
    for idx, i in enumerate(p):
        if i == '(':
            left_count += 1
        elif i == ')':
            right_count += 1
        # 더이상 나눠질 수 없는 올바른 괄호문자열 찾음
        if left_count == right_count:
            return p[:idx + 1], p[idx + 1:] # u,v


def isBalanced(u):
    stack = []

    for i in u:
        if i == '(':
            stack.append(i)
        else:
          # ")" 인 경우
          # stack이 비어있다면, ")"가 들어가서는 안됨
            if not stack:
              # 따라서 False return
                return False
            stack.pop()
    return True

해당 문제의 모범 답안을 살펴보면 문자열을 분리해주는 함수, 문제에서 주어진 조건이었지만

균형잡힌 문자열인지 확인하는 함수, 그리고 최종적으로 결과를 만들어주는 함수까지 3개의

함수를 이용합니다. 이렇게 단계별로 필요한 함수로 나눠서 개발하는 것을 더 연습하고,

재귀함수의 적용과도 밀접한 연관이 있는 문제인만큼 잘 숙지하고 넘어가야 할 것 같습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady