[class2]백준 4779번(칸토어 집합) - 코딩테스트 23일차(2025.02.13)

문제유형

재귀 함수

풀이 방법 도출 과정

1. 3^N 개가 있는 문자열을 만든다.

2. 문자열을 3등분 한 뒤 가운데 문자열을 공백으로 바꾼다.

3. 나머지 2개를 3등분하고 가운데를 공백으로 바꾼다.

4. 모든 선의 길이가 1이면 멈춘다.

5. 이걸 출력하는 프로그램을 만들면 된다.

6. 이걸 재귀함수로 만들어보도록 하겠다. 

시간 복잡도

• 각 단계에서 N만큼의 문자열 결합 연산이 발생.
• 재귀적으로 N/3 크기의 문제를 두 번 호출.
• 즉, O(N/3)이 시간복잡도

 

코드 및 간단설명

재귀함수를 사용하여 문제를 풀었다. 

def line_one(N):
    if N == 1:
        return '-'
    
    prev = line_one(N // 3)
    space = ' ' * (N // 3)
    
    return prev + space + prev

while True:
    try:
        N = int(input())
        print(line_one(3**N))
    except EOFError:
        break

다른 풀이

1) 다른 재귀적 방법

아래는 재귀적으로 문자열을 직접 생성하는 대신, 전체 문자열을 리스트로 구성한 후 중간 부분을 재귀적으로 공백으로 채워나가는 방법이다.

def cantor(arr, start, end):
    # 구간 길이가 3보다 작으면 더 이상 나눌 수 없음
    if end - start < 3:
        return
    # 현재 구간을 3등분할 때 한 구간의 길이
    third = (end - start) // 3
    
    # 중간 구간을 공백으로 변경
    for i in range(start + third, start + 2 * third):
        arr[i] = ' '
    
    # 왼쪽, 오른쪽 구간에 대해 재귀 호출
    cantor(arr, start, start + third)
    cantor(arr, start + 2 * third, end)

while True:
    try:
        n = int(input())
        length = 3 ** n
        # 전체 문자열을 '-'로 채운 리스트 생성
        arr = ['-'] * length
        
        # 리스트 내에서 중간 부분을 재귀적으로 공백 처리
        cantor(arr, 0, length)
        
        # 리스트를 문자열로 합쳐서 출력
        print(''.join(arr))
    except EOFError:
        break

설명

1. 초기 리스트 구성

• n을 입력받고, 길이를 3**n으로 정한다.
• 전체를 '-'로 채운 리스트 arr를 만든다.

2. cantor 함수

• 이 함수는 arr 리스트의 start부터 end(미포함) 구간에 대해 중간 부분을 공백(' ')으로 바꾸고, 좌우 부분에 대해 같은 작업을 재귀적으로 수행한다.
• 만약 구간의 길이가 3보다 작으면 더 이상 분할할 수 없으므로 재귀를 종료한다.
• 현재 구간의 길이를 3으로 나눈 third를 계산하여, 중간 구간(start+third부터 start+2*third까지)을 공백으로 바꾼다.
• 이후 좌측 구간(start ~ start+third)과 우측 구간(start+2*third ~ end)에 대해 재귀 호출을 수행한다.

3. 입출력 처리

• while True 루프 내에서 사용자 입력을 받고, EOF(파일의 끝) 예외 발생 시 종료한다.
• 입력받은 n에 대해 길이가 3**n인 리스트를 만든 후 cantor 함수를 호출하여 중간 부분을 공백으로 변경한다.
• 최종 결과 리스트를 ''.join(arr)로 문자열로 변환하여 출력한다.