[programmers] 프로그래머스 괄호 변환(Python)

(주)그렙

[programmers] 프로그래머스 괄호 변환

(Python)

(글쓴날 : 2020.06.19)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 괄호 변환

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60058

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

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

소괄호들로 이루어진 문자열이 주어질 때, 올바른 괄호 문자열로 변환하는 문제입니다.

 

저의 경우, Python을 사용했습니다.

이 문제의 경우, 문제를 해결하는 로직이 서술되어 있기 때문에 해당 로직을 그대로 구현해 문제를 해결했습니다.

문자열 w를 u, v로 분리하는 함수와, 문자열 u가 올바른 괄호 문자열인지 확인하는 함수, 이 두 가지 함수만 따로 작성한 뒤, 문제에 서술되어 있는 로직을 그대로 구현하시면 됩니다.

---

3) 코드

 

* Python 코드

# 문자열 w를 u, v로 분리하는 함수
def divide(w):
    openP = 0
    closeP = 0
    
    for i in range(len(w)):
        if w[i] == '(':
            openP += 1
        else:
            closeP += 1
        if openP == closeP:
            return w[:i + 1], w[i + 1:]
 
 
# 문자열 u가 올바른 괄호 문자열인지 확인하는 함수
def isBalanced(u):
    stack = []
    
    for p in u:
        if p == '(':
            stack.append(p)
        else:
            if not stack:
                return False
            stack.pop()
            
    return True
 
 
def solution(w):
    # 과정 1
    if not w:
        return ""
    
    # 과정 2
    u, v = divide(w)
    
    # 과정 3
    if isBalanced(u):
        # 과정 3-1
        return u + solution(v)
    # 과정 4
    else:
        # 과정 4-1
        answer = '('
        # 과정 4-2
        answer += solution(v)
        # 과정 4-3
        answer += ')'
        
        # 과정 4-4
        for p in u[1:len(u) - 1]:
            if p == '(':
                answer += ')'
            else:
                answer += '('
        
        # 과정 4-5
        return answer

---