[이코테] 재귀,구현 - 괄호 변환 with 파이썬

JIN KANG·2022년 10월 18일

algorithm python recursion 이코테 코딩테스트

이코테

목록 보기

18/29

1. 문제

프로그래머스 카카오2020공채 문제와 동일 , 링크
용어 정리
- () 갯수가 같다면, 균형잡힌 괄호 문자열
- () 짝도 모두 맞을 경우 , 올바른 괄호 문자열
단계별 구현 동작 (w가 균형잡힌 문자열 이라면, 올바른 괄호 문자열로 변환할 수 있다.)

입력이 빈 문자열인 경우 , 빈 문자열을 반환
w를 두 균형잡힌 괄호 문자열 u, v로 분리
-u는 균형잡힌 문자열로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있다.
문자열 u가 올바른 괄호 문자열 이라면, 문자열 v에 대해 1단계부터 다시 수행한다.

수행한 결과 문자열을 u에 이어 붙힌 후 반환

u가 올바른 괄호 문자열이 아니라면 다음과 같은 과정
-4-1. 빈 문자열에 첫 번째 문자로 "("를 붙인다.
-4-2. v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.
-4-3. ")"를 다시 붙인다.
-4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다.
-생성된 문자열을 반환한다.

문제 요약 : 균형잡힌 괄호 문자열 p 가 매개변수로 주어질 때, 주어진 알고리즘을 수행해, 올바른 괄호 문자열로 변환한 결과를 return한다.

입출력 예시

2. 아이디어

시키는대로 하면된다. 근데 그게 쉽지 않다.
- 균형잡힌 괄호로 u,v를 나누는 함수, 올바른 괄호인지 확인하는 함수를 만든다.
- 전체 절차를 조건에 맞게 재귀적으로 구현한다.

3. 예제코드

# 균형잡힌 괄호 문자열까지 인덱스 나오는 함수 u, v 분리용
def balanced_index(p):
    count = 0                 # 여는 괄호 수 
    for i in range(len(p)):
        if p[i] == '(':
            count += 1
        else :
            count -= 1
        if count == 0 :       # 여는괄호, 닫는괄호 같아지는 즉시 
            return i
# 올바른 괄호 확인 함수 
def check_proper(p):
    count = 0  # 여는 괄호 수 저장 
    for i in p :
        if i == '(':
            count += 1
        else :
            if count == 0:   # 여는 괄호 없는 상태로 닫는 괄호를 만났는지 확인 
                return False 
            count -=1
            
    return True  # 쌍이 맞으면 True

def solution(p):
    answer = ''
    # 1단계 , 빈문자열인가 
    if p == '':
        return answer 
    # 2단계 , 문자열 나누기 
    index = balanced_index(p)
    u = p[:index+1]
    v = p[index+1:]
    # 3단계 , u가 올바른 괄호 문자열이라면, u 뒤에 v만 재귀 실행 후 붙인다.
    if check_proper(u):
        answer = u + solution(v)
    # 4단계 , u가 올바른 괄호 문자열이 아니면, 
    else:
        answer = "("   # 4-1 단계 , 빈 문자열에 첫번째 여는 괄호를 붙인다.
        answer += solution(v)  # 4-2 단계, v에 대해서 재귀적으로 실행한 결과를 붙인다. 
        answer += ")"  # 4-3 단계 , 닫는 괄호를 붙인다. 
        u = list(u[1:-1])   # 4-4 단계, 첫문자와 끝문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다. 
        for i in range(len(u)): 
            if u[i] == "(": 
                u[i] = ')'
            else :
                u[i] = '('
                
        answer += ''.join(u)
        
    return answer