사용 언어: python 3.9.5

❓ Problem

문제 설명

문제 링크

난이도

level 2

🚩 Solution

실패한 코드

시도 01)

1. 접근법

문제에 주어진 구현법대로 하나씩 따라하다가 재귀가 나와서 아차 함....

시간이 짧아서 다 풀지 못함

2. 코드

def solution(p):
    # 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    
    if p == '':
        return ''
    
    answer = ''
    
    p = list(p)
    print(p)
    l_cnt: int = 0
    r_cnt: int = 0
    u = []
    v = []
    temp = []
    # 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
    # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    for i, val in enumerate(p):
        if val == '(':
            l_cnt += 1
        else:
            r_cnt += 1
        
        if l_cnt == r_cnt:
            u.append(p[:i+1])
            v.append(p[i:])
            l_cnt = 0
            r_cnt = 0
            
            
    
    q = []
    correct = True
    
    
    for i in u:
        if i == '(':
            q.append(i)
        else:
            if q.empty():
                correct = False
                break
            q.pop(0)
    # 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
    if correct == True:
        
        # 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
        
            
            
    # 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
    else:
        
        # 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
        # 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
        # 4-3. ')'를 다시 붙입니다. 
        # 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
        # 4-5. 생성된 문자열을 반환합니다.

    
    
    return answer

3. 시간복잡도

$O(n)$

4. 결과

실패

원인: 틀렸습니다
시간이 부족해서 코드를 다 못짬

5. 소요 시간

20분

📕 피드백

1. 검색한 내용

2. 실수

3. 발전 방향 (개선/추가사항)

처음부터 문제를 꼼꼼하게 읽고 시작하자

4. 다른 사람 풀이

풀이1)

• 링크

https://hellominchan.tistory.com/352

• 접근법

문제에서 주어진 대로 푼다

• 코드

# 문자열 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

• 배울 점