카카오 2020 기출
문제 링크

스택

문자열 관련 문제는 보통 스택부터 떠올린다.

이 문제 또한 2개의 스택을 활용하면 어렵지 않게 풀 수 있다.

스도 코드

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

보통 로직 설계가 제일 어려운 부분인데 문제에서 친절히 설명해줬다.
차근차근 따라가며 코드로 변환하였다.

사용자 정의 함수

• separate(p) = u,v 👉🏻 스도 코드 #2
• check(u) = Boolean 👉🏻 스도 코드 #3/#4
• reverse_par(p) = 뒤집어진 괄호 문자열 👉🏻 스도 코드 #4-4

코드

# 문자열을 u,v로 분리
def separate(p):
    # print('start sep')
    left,right = 0,0
    i = 0 
    while True:
        if left>0 and right>0 and left==right:
            u = p[:i]
            if u == p:
                v = ''
            else:
                v = p[i:]
            break
        if p[i] == '(':
            left += 1
        if p[i] == ')':
            right += 1
        i += 1
    return u,v
# "올바른 괄호 문자열" 검사
def check(u):
    u = list(u)
    stack = list()
    while u:
        stack.append(u.pop())
        if len(stack)>=2 and stack[-1] == '(' and stack[-2] == ')':
            stack.pop()
            stack.pop()
    if stack:
        return False
    return True
# 괄호 방향 뒤집개
def reverse_par(p):
    p = list(p)
    for i in range(len(p)):
        if p[i] == '(':
            p[i] = ')'
        else:
            p[i] = '('
    return ''.join(p)
def solution(p):
    answer = ''
    #1
    if p == '':
        return ''
    #2
    u,v = separate(p)
    # print('u = {0}, v={1}'.format(u,v))
    #3
    if check(u):
        #3-1
        return u+solution(v)
    #4    
    else:
        #4-1
        answer += '('
        #4-2
        answer += solution(v)
        #4-3
        answer += ')'
        #4-4
        answer += reverse_par(u[1:len(u)-1])
    return answer