[카카오] 괄호 변환

출처:: 2020 카카오 신입 공채 1차 https://programmers.co.kr/learn/courses/30/lessons/60058

분류:: 구현

 

1. 문제 이해 및 해결과정

  

2. 풀이방법

   1. 구현

#올바른 괄호 문자열인지 판단
def paren(w):
    cnt=0 
    for x in w:
        if x=='(':
            cnt+=1
        else:
            if cnt==0:
                return False
            cnt-=1
    return True

#균형잡힌 괄호 문자열인지 
def balanced_paren(p):
    leng=len(p)
    left=right=0
    for i in range(leng):
        if p[i]=='(':
            left+=1
        else:
            right+=1
        if left==right:
            return i
        
def solution(p): #p는 균형잡힌 괄호 문자열
    empty = ''
    leng=len(p)
    left=right=0
    if leng==0: #빈 문자열이면, 빈 문자열 반환
        return empty
    index=balanced_paren(p)
    u=p[:index+1]
    v=p[index+1:leng]
    if paren(u): #올바른 괄호 문자열이면
        empty= u + solution(v) #u에 이어 붙인 후 반환 
    else:
        empty='('
        empty+= solution(v)
        empty+= ')'
        u=u[1:len(u)-1] 
        nu=""
        for x in u:
            if x==')':
                nu+='('
            else:
                nu+=')'
        empty+=nu
    return empty

   2. 같은 풀이

def balanced_paren(p):
    cnt=0
    for i in range(len(p)):
        if p[i]=='(':
            cnt+=1
        else:
            cnt-=1
        if cnt==0:
            return i 
        #전제가 균형잡힌 문자열을 받은 것이므로 return 이 없을 순 없음 

def paren(p):
    cnt=0
    for x in p:
        if x=='(':
            cnt+=1
        else:
            if cnt==0:
                return False
            cnt-=1
    return True

def solution(p):#p는 균형잡힌 문자열
    answer = ''
    if p=='':
        return answer
    index= balanced_paren(p)
    u=p[:index+1]
    v=p[index+1:]
    
    if paren(u):
        answer=u+solution(v)
    else: #올바른 문자열이 아니면
        answer='('
        answer+=solution(v)
        answer+=')'
        u=list(u[1:-1])
        for i in range(len(u)):
            if u[i]==')':
                u[i]='('
            else:
                u[i]=')'
        answer+="".join(u)
    return answer

3. 오답원인

 

4. 알게된 점