백준 재귀 단계: 4779번 칸토어 집합

🛎️ 4779번

문자열 "---------------------------"을
재귀 함수를 사용해서 "- -   - -         - -   - -"로 바꿔야한다.

정답 코드

def cantor(x_list):
    if ( len(x_list) <= 1 ):
        return x_list
    a = int(len(x_list)/3)
    t_list = " " * a
    left_list = x_list[:a]
    right_list = x_list[-a:]
    y_list = cantor(left_list) + t_list + cantor(right_list)
    return y_list
    
    
def x_list_creat(n) :
    c_str = "-"
    i = 0
    x_list = c_str*(3**n)
    return x_list

a_list = []

while True :
    try:
        n = int(input())
        a_list.append(n)
    except:
        break

for i in a_list:
    print(cantor(x_list_creat(i)))

🤔 해결 아이디어

아직 해결하지는 못했지만...ㅎ 병합 정렬에서 사용했던 재귀 알고리즘을 해결 해봤다.

내가 생각하는 병합정렬의 핵심 알고리즘

def : 재귀 함수
문자열을 나눠서 각각 재귀를 돌린다.
	중간 결과 : 나눠진 문자열의 내용물이 정렬이 된다.
나눠진 문자열을 가지고 정렬을 한다.

🎯 최종 목표 : 문자열을 계속해서 3등분으로 나누고, 가운데가 공백으로
⭐ 중간 중간의 목표 : 문자열을 3등분해서 중간을 공백으로 바꾼 문자열 : "- -"

따라서, 전체 문자열을 3등분을 했을 때, 첫 부분과 마지막 부분은 ⭐계속해서 중간목표형태로 바꿔주어여한다.
👉 재귀 알고리즘!!

따라서 내가 고안한 알고리즘

1. 문자열을 3등분한다.
2. 첫 부분, 마지막 부분을 재귀함수로 돌린다.
3. 첫 부분과 마지막 부분이 원하는 문자열의 형태 (- -)가 된다.
4. 중간 부분을 공백으로 바꾼다.

📌 원하는 문자열의 형태를 만들어주는 재귀 함수, 문자열을 나눠서 각각 재귀를 돌린다!
🤔 그러면 각각의 문자열을 나눠서 재귀함수를 돌려보자!!
👉 실패 ! 🤮

실패 코드

def cantor(x_list):
    if ( len(x_list) <= 1 ):
        return x_list
    a = int(len(x_list)/3)
    t_list = " " * a
    x_list.replace(x_list[:a],cantor(x_list[:a]))
    x_list.replace(x_list[a+1:a*2+1],t_list)
    x_list.replace(x_list[-a:],cantor(x_list[-a:]))

⭐ 실패 이유 1. 파이썬의 문자열은 불변 객체

파이썬의 문자열은 불변 객체이다.
따라서, 문자열을 바꾸는 것이 아니라 새로운 문자열을 반환한다.
x_list.replace(x_list[:a],cantor(x_list[:a]))의 결과가 x_list에 바뀌는 것이 아니고 새로운 문자열이 생성된다.
📌 따라서 바꾼 문자열을 기존 문자열에 반영하고 싶으면 "=" 연산자를 활용해 저장해야한다.

⭐ 실패 이유 2. 파이썬의 replace는 인덱스를 활용할 수 없다.

파이썬의 replace는 첫번째 인자를 해당 문자열에서 모두 찾아서, 두번째 인자로 바꾸어준다.
📌 해당 위치의 문자열을 바꾸는 것이 아님을 기억하자.

🖥️ 코드로 확인해보자.
내가 기대하는 최종 문자열은 "123456789"이지만, 실제 문자열은 789789789가 되는 것을 알 수 있다.

x_list = "---------"
a = len(x_list)//3

x_list = x_list.replace(x_list[:a],"123")
print(x_list) #123123123
x_list = x_list.replace(x_list[a:a*2],"456")
print(x_list) #456456456
x_list = x_list.replace(x_list[-a:],"789")
print(x_list) #789789789

그러면 어떻게 해야할까?

파이썬의 문자열을 바꾸는 가장 간단한 방법은 기존 문자열 = 원하는 문자열1+ 원하는 문자열2 + 원하는 문자열3이다.
또한 병렬정렬에서는 자료형이 리스트였다. 따라서 변경이 가능했지만 문자열은 변경이 반영되지 않는다.(불변객체)

def cantor(x_list):
    if ( len(x_list) <= 1 ):
        return x_list
    a = int(len(x_list)/3)
    t_list = " " * a
    x_list = cantor(x_list[:a]) + t_list + cantor(x_list[-a:])
    return x_list

📌 여러줄로 된 입력 받기

a_list = []

while True :
    try:
        n = int(input())
        a_list.append(n)
    except:
        break