[Python] 백준 4779 칸토어 집합

다시

문제 분석

• 칸토어 집합 : 0~1사이의 실수로 이루어진 집합
• 구간 [0,1]에서 시작해서 각 구간을 3등분 하여 가운데 구간을 반복적으로 제외
• 모든 선의 길이가 1일대 까지 계속
• 입력 받는 n -> 3^n
• - 에서 공백으로 전환
• 파일의 끝에서 입력을 멈춘다?

 

코드 설계

• 종료조건 : -이 하나면 종료
• 3등분을 해서 가운데 지우는 함수를 구현하여 재귀 (반복)

1. n 입력 / 입력은 언제까지 받을 것인가? -> 파일이 끝날때까지/ 더 이상 입력이 없으면
2. str에 3^n개만큼의 "-" : 제곱을 어떻게 구현할 것인가 - 이중 반복문? 우선은 "---"를 n번 붙이는 걸로
3. 그리고 어떻게 -를 이어 붙일것인가 : 파이썬은 문자열을 +로 합칠 수 있다.
4. 재귀함수
5. "-" 부분만 다시 입력
6. 만약 입력된 문자열이 "-"이면 return
7. 아니면 입력된 문자열 3등분하고 공백 처리 어쩌구 하고
8. 붙이기
9. 붙여진 부분 중 "-"만 함수에 다시 입력

실패..

• 반복해서 자르므로 재귀 이용
• 시작점(s)을 기준으로 s + (n//3) 부터 s + (n//3) * 2 까지 사이를 지워주면 됨
• 파이썬 ** : ex) x**y = x^y
• 파이썬은 문자열 부분 변경이 불가능 하므로 문자열을 list로 바꿔준 후에 index로 접근해야한다.

 

정답 코드

import sys
input = sys.stdin.readline

def cut(n, start, end):
    if n == 0 :
        return

    # 3등분
    div = (end - start + 1) // 3

    # 왼쪽 재귀
    cut(div, start, start + div -1)

    # 가운데 공백으로
    for i in range(start + div, start + div * 2) :
        ans[i] = ' '

    # 오른쪽 재귀
    cut(n-1, start + div * 2, start + div * 3 -1)

while True :
    try :
        n = int(input())
        ans = ['-'] * (3**n) # ***
        cut(n, 0, 3**n-1)
        print(''.join(ans))
    except:
        break