[programmers] 괄호변환

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

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

 

• 이문제는 스택을 이용해서 괄호를 만들 수 있을지 없을지를 물어보는 문제가 아닌, 주어진 조건에 맞게 구현을 하면 되는 문제입니다.

• 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. 생성된 문자열을 반환합니다.

• 위 조건들에 맞게 구현을 해주면 됩니다. 자세한 내용은 주석을 참고해주시면 감사하겠습니다.

 

def divide(w):
    # 2번 조건 구현
    open_cnt = 0
    close_cnt = 0
    for i in range(len(w)):
        if w[i] == "(":
            open_cnt += 1
        else:
            close_cnt += 1
            # 균형잡힌 괄호문자열일경우,
        if open_cnt == close_cnt:
            # 분리한다.
            return w[:i+1], w[i+1:]

def perfectString(u): # 3번조건구현 함수
    stack = []
    for i in u:
        if i == "(":
            # 스택에 넣어주고
            stack.append(i)
        else:
            # 만약에 ) 일 때 스택에 없으면
            if not stack:
                # 올바른 괄호 문자열이 아니다.
                return False
            # 스택에 있으면 짝을 맞춰주고 pop
            stack.pop()
    return True

def solution(p):
    if not p: #1번
        return ""
    u,v = divide(p) #2번
    if perfectString(u): #3번
        return u + solution(v)
    
    else: #4번
        tmp = "(" # 4-1번
        tmp += solution(v) # 4-2번
        tmp += ")" # 4-3번
        for i in u[1:len(u)-1]: # 4-4번
            if i == '(':
                tmp += ')'
            else:
                tmp += '('
                
    return tmp