[PG/Python] 괄호 변환

📌 문제

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

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

 

📌 문제 접근 방법

1. 스택을 활용하여 올바른 괄호열을 판단하는 함수를 만들었다.
   
   1. 여는 괄호를 만나면 스택 안에 넣는다.
   2. 닫는 괄호를 만나면 스택에서 괄호 하나를 pop 한다.
   3. 문자열이 끝나지 않았는데 스택에서 pop을 할 수 없거나, 문자열이 끝났는데 스택에 남는 괄호가 있다면 올바른 괄호열이 될 수 없다.
2. 그 후에는 문제에서 주어진 방식을 그대로 따라서 변환할 수 있도록 함수를 짰다.

 

📌 코드

def is_correct(string):
    stack = []

    for s in string:
        if s == '(':
            stack.append(s)
        else:
            if not stack:
                return False
            stack.pop()
    
    if stack:
        return False
    
    return True


def solution(p):
    if is_correct(p):
        return p

    answer = ''

    def change_correct(string):
        nonlocal answer
        
        if not string:
            return string

        u = [string[0]]
        v = []

        for i in range(1, len(string)):
            if u.count('(') == u.count(')'):
                v = string[i:]
                break
            else:
                u.append(string[i])
        
        if is_correct(u):
            answer += ''.join(u)
            change_correct(''.join(v))
        else:
            answer += '('
            change_correct(''.join(v))
            answer += ')'
            for i in range(1, len(u)-1):
                if u[i] == '(':
                    answer += ')'
                else:
                    answer += '('
    
    change_correct(p)

    return answer