Py) 프로그래머스 60058 괄호변환

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

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

 

1차 시도: 1시간 40분

 

0. 입출력

 

1. 김예고리즘

1-1. 로직

check correct(w):
    u 찾는 코드     stack, 빠져나온거 u에 추가,                   // 틀림!
                  남아있는 개수 확인, 스택에 들어있는 수가 남은거보다 많을 때 정지
    v 나머지

    # u가 올바른지 아닌지 판단
    올바른 문자열이라면
        v가 빈 문자열이 아니라면 check correct(v)
        return u+v

    올바른 문자열이 아니라면
        빈문자열 ( + correct(v) + )
        u의 첫번째, 마지막 문자 제거, 괄호 방향 뒤집어서 뒤에 붙임
    return 최종 문자열

 

1.2 코드

# 날려버림,,,
    stack = []
    u = []
    v = []
    for i in range(len(w)):
        if len(stack) == 0:
            stack.append(w[i])
        else:
            if stack[-1] == '(' and w[i] == ')':
                u.append(stack.pop())
                u.append(w[i])
                continue
            else:
                stack.append(w[i])
        if len(stack) > len(w[i:]):
            v+=stack
            v+=w[i:]        # append하면 []도 그대로 들어감
            break

 

맞춘 코드

def correct(w):
    open = close = 0

    for i in range(len(w)):
        if w[i] == '(':
            open += 1
        else:
            close += 1

        if open == close:
            u = "".join(w[:i+1])
            v = "".join(w[i+1:])
            break


    # 올바른 문자열
    empty = ""      # 선언도 잘못함
    new_u = ""
    if u[0] == '(' and u[-1] == ')':    # 올바름
        if len(v) == 0:
            return u
        else:
            return u+correct(v)
    else:
        if len(v) == 0:
            empty+='('+""+')'        # append나 + 하면 list로 바뀜
            empty = ''.join(empty)
        else:
            empty += '('+correct(v)+')'
            empty = ''.join(empty)
            # empty.append(correct(v))
            # empty.append(')')
        # u 처음, 마지막 제거, 괄호 방향 뒤집어서 뒤에 붙이기
        for j in range(1, len(u)-1):
            if u[j] == '(':
                new_u += ')'
            else:
                new_u += '('
        return empty+new_u


def solution(p):
    answer = ''
    p = list(p)
    answer = correct(p)
    return answer

 

1.3 문제점 & 놓친 것:
1. 처음에 균형잡힌 문자열인데 처음부터 올바른 문자열로 열심히 나눔..
2. u 찾는 코드에서 stack을 사용하고 stack에 들어있는 원소의 수가 아직 검토하지 않은 원소의 수보다 많으면 종료하게 함  --> 문제점: ))((() 이런 경우에 못함
3. ""랑 [] 제대로 선언 안해줘서 중간에 list가 섞여 들어갔고 그 결과

,,,

이와 같은 끔찍한 혼종이 탄생함.

1) 인덱스 슬라이싱을 사용하면 list로 바뀜
2) empty = []와 같이 변수들을 list로 선언해버림
3) append나 + 사용해도 list로 바뀜

4. 그리고 len(v)==0의 경우를 생각 안해줘서 빈 문자열이 재귀로 넘어갔고, 시간만 잡아먹음. 애초에 넘어가지도 않았던거 같다.