[백준][19단계 재귀] 4779번 /칸토어 집합 (파이썬/Python)

1. 문제 설명

2. 코드

import sys

def carve(chars, start, length):
    if length == 1:
        return
    third = length // 3
    for i in range(start + third, start + 2*third):
        chars[i] = ' '
    carve(chars, start, third)
    carve(chars, start + 2*third, third)

Ns = [int(s.strip()) for s in sys.stdin.read().splitlines() if s.strip()]

for n in Ns:
    length = 3 ** n
    chars = ['-'] * length
    carve(chars, 0, length)
    print(''.join(chars))

3. 풀이 과정

칸토어 집합의 재귀 함수를 먼저 정의한다.

'-'로 이루어진 문자열 chars와

시작 인덱스 start

chars의 길이 length로 이루어진 함수 carve()는 다음과 같이 동작한다.

length가 1이 되면 반환하여 재귀를 끝낸다.

3등분으로 나누어 third에 값을 저장하고

가운데 구간(start+thrid, start+2*thrid)를 공백 ' '으로 대체한다.

왼쪽 구간 재귀 carve(chars, start, third)와 오른쪽 구간 재귀 carve(chars,start+2*third,third)를 진행한다.

 

Ns에 N값들을 저장한다.

sys.stdin.read().splitlines()로 모든 줄의 N값들을 한번에 받아 리스트로 저장한다.

오류 방지를 위해 if s.strip() 조건을 달아주고, 좌우 공백을 제거한 s.strip()을 int()로 감싸서 리스트로 저장한다.

 

Ns를 for문으로 하나씩 받아서 

length (3의 n제곱)과 chars (legnth만큼의 ['-'])를 구해주고 carve(chars,0,length)로 칸토어 집합을 구해준다.

''.join() 빈 구분자로 연결시켜서 출력한다.

4. 자투리 개념

• ''.join()
  - 리스트 안의 문자열 요소들을 구분자 기준으로 연결(join)하는 함수
  - 빈 구분자이므로 아무 문자도 넣지 않고 단순히 붙이겠다는 의미