[프로그래머스] 카카오공채 2019 - 괄호변환

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

프로그래머스

---

주저리: 역시 문제 길이가 긴 문제는 친절한데 읽고 해석하는게 귀찮아서

대놓고 알려준 힌트임에도 불구하고... 못풀고 헤메는 경우가 있다.

문제가 긴것은 친절한 문제이고, 해석과 이해를 할 수 있다면 풀도록 설계된 문제이다 ㅠㅠ

문제를 잘 읽자.

 

[코드]

def recursion(p):
    #p가 비어있있는 문자열이라면
    if len(p)==0:
        return p

    #p를 균형잡힌 두 문자열로 분리한다.
    num=0
    for i in range(len(p)):
        if p[i]=='(':
            num+=1
        else:
            num-=1

        if num==0:
            u=p[:i+1]
            v=p[i+1:]
            break
        
    #u가 올바른 문자열이라면
    if isCorrect(u):
        return u+recursion(v)
    
    #u가 올바른 문자열이 아니라면
    #4-1. 비어있는 문자열에 ( 를 붙인다.
    #4-2. 문자열 v에 대해 1단계로부터 재귀적 수행한 결과 문자열을 이어붙인다.
    #4-3. )을 다시 붙인다.
    tmp='('+recursion(v)+')'
    
    #4-4. u의 첫번째와 마지막 문자를 제거하고 나머지 문자열의 괄호방향을 뒤집어서 뒤에 붙인다.
    #길이가 2보다 크다면
    if len(u)>2:
        for i in range(1,len(u)-1):
            if u[i]=='(':
                tmp+=')'
            else:
                tmp+='('
    return tmp

#올바른 괄호문자인지 확인해주는 함수이다.
#빈문자열도 올바른 괄호문자열로 체크된다.
def isCorrect(input_str):
    left_cover=[]
    for i in input_str:
        if i=='(':
            left_cover.append(i)
        else:#i==')'
            if len(left_cover)==0:
                return False
            left_cover.pop()
    if len(left_cover)>0:
        return False
    return True
            
            
def solution(p):
    #p는 올바른 문자열이다.
    if isCorrect(p):
        return p
    #p는 올바른 문자열이 아니라면
    return recursion(p)

---

[실패 코드와 결과]

def isCorrect(p):
    input_p=list(p)
    right_cover=[]
    while len(input_p)>0:
        now=input_p[-1]
        if now==')':
            right_cover.append(input_p.pop())
        else:
            if len(right_cover)>0:
                right_cover.pop()
                input_p.pop()
            elif len(right_cover)==0:
                return False
    if(len(input_p)>0) or (len(right_cover)>0):
        return False
    return True
    
    
def change2Correct(u,v):
    #u가 올바른 문자열이라면
    if isCorrect(u):
        return u+v
    #u가 올바르지 않은 문자열이라면
    cover={')':0, '(':0}
    for i in range(len(u)):
        if u[i]=='(':
            cover['(']+=1
        else:
            cover[')']+=1
        if(cover['(']>0 and cover[')']>0) and (cover['(']==cover[')']):
            x=u[:i+1]
            y=u[i+1:]
            break
    #y의 길이가 0보다 크다면
    if len(y)>0:
        return change2Correct(x,'')+change2Correct(y,'')
    #올바른 문자열로 바꾼다.
    for i in range(len(x)):
        if x[i]=='(':
            y+=')'
        else:
            y+='('
    return change2Correct(y,'')
    

def solution(p):
    if len(p)==0 or isCorrect(p):
        return p
    return change2Correct(u=p, v='')

테스트 케이스 모두 통과

100점 만점 중 20점을 받았다.

일단은 O(N)이므로 시간초과가 안나왔다.