문제
칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.
전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.
1. -가 3N개 있는 문자열에서 시작한다.
2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.
3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.
예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.
---------------------------
여기서 가운데 문자열을 공백으로 바꾼다.
--------- ---------
남은 두 선의 가운데 문자열을 공백으로 바꾼다.
--- --- --- ---
한번 더
- - - - - - - -
모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/4779
입력
입력을 여러 줄로 이루어져 있다.
각 줄에 N이 주어진다.
파일의 끝에서 입력을 멈춘다.
N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.
출력
입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.
예제
# input
0
1
3
2
# output
-
- -
- - - - - - - -
- - - -문제 풀이
import sys
input = sys.stdin.readline
def cantor(S):
length = len(S) // 3
# 문자열의 길이가 1이 되었을 때, 문자열을 반환
if length == 0:
return S
# 재귀적으로 중간 부분을 공백으로 바꿔줌
part1 = cantor(S[:length])
part2 = ' ' * length
part3 = cantor(S[length * 2:])
return part1 + part2 + part3
while True:
try:
# 입력값을 받아서 초기 문자열 생성
N = int(input())
S = '-' * (3**N)
# 칸토어 집합 생성 및 출력
print(cantor(S))
except:
break재귀 과정은 단계별로 아래와 같습니다.
초기 문자열 S는 27개의 '-'로 구성
S = '---------------------------'
1단계: 첫 번째 호출 cantor(S)
문자열 S를 세 부분으로 나누어 처리
part1 = '---------'
part2 = ' '
part3 = '---------'
2단계: part1, part3에 대해 cantor 재귀 호출
part1와 part3는 각각 9개의 '-'로 구성
part1 = '---------'
part2 = ' '
part3 = '---------'
각 부분을 다시 세 부분으로 나누고 가운데 부분을 공백으로
part1 = '---'
part2 = ' '
part3 = '---'
3단계: 각 부분에 대해 다시 cantor 재귀 호출
part1, part2, part3는 각각 3개의 '-'로 구성
part1 = '-'
part2 = ' '
part3 = '-'
이제 각 부분의 길이가 1이 되므로 더 이상 나눌 수 없고, 그대로 반환파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
