(Python) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 괄호 변환

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

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

 

• 해설 :

'(' 과 ')'의 개수가 같다면 이를 '균형잡힌 괄호 문자열' 이라고 부른다. 또한, 균형잡힌 괄호 문자열이면서 '(' 과 ')'의 열고 닫는 짝이 맞다면 이를 '올바른 괄호 문자열' 이라고 부른다.  균형잡힌 괄호 문자열이 주어질 때 이를 올바른 괄호 문자열로 변환해서 반환하면 된다.

 

 

 

• 풀이 :

프로그래머스에서 이 문제를 level 2로 판단하였는데 개인적으로 level 3이여도 충분한 문제라고 생각한다. 우선 문제를 이해하는데에 시간이 오래 걸린다. 또한,  구현해야 하는 로직이 여러개이고 하나라도 틀에 벗어난다면 완전히 다른 정답값이 출력되기 때문이다.  우선 재귀적으로 함수를 수행하게 만들고  올바른 괄호 문자열인지 판별하는 함수와 

두 개의 균형잡힌 괄호 문자열로 변환하는 함수,  

4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

의 과정을 수행하는 함수, 총 3개를 구현하였다. 

 

이후 재귀적으로 이를 실행하며 올바른 괄호 문자열인지 체크하면서 진행하도록 구현하였다. 

 

def correct(s):
    cnt = 0
    for i in s:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            return False
    return cnt == 0
    
def divide(s):
    cnt = 0
    u = []
    v = []
    for idx,i in enumerate(s):
        u.append(i)
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt == 0:
            break
    for i in range(idx+1,len(s)):
        v.append(s[i])
    return [''.join(u),''.join(v)]
 
def rev(s):
    ret = ""
    dic = {
        "(" : ")",
        ")" : "("
    }
    for i in s:
        ret += dic[i]
    return ret
 
def dfs(s):
    if correct(s):
        return s
    u,v = divide(s)
    if correct(u):
        return u+dfs(v)
    else:
        return "(" + dfs(v) + ")" + rev(u[1:-1]) 
    
    
    
def solution(p):
    if p == "":
        return ""
    answer = dfs(p)
    return answer