[백준] 4779번 칸토어 집합 파이썬 정답 코드

4779번: 칸토어 집합

---

1. 문제 내용

 

 

2. 접근 방식

 단계별로 풀어보기에서 '재귀' 카테고리로 들어갔었기 때문에 재귀를 활용해야 한다는 것은 알고 있었다. 그러나 팩토리얼처럼 귀여운 재귀 문제 말곤 풀어본 적이 없어서 꽤 오랜 시간 고민했다. 스트링을 3등분하고 가운데 구간을 공백(띄어쓰기)로 만드는 것은 쉽지만, 문제는 이를 어떻게 재귀 함수에 녹이냐는 것이었다!

 

• 병합 정렬에서 힌트를 얻다.

 이 문제를 풀기 전에 병합 정렬 문제를 시도했다가 포기했는데, 뜻밖에도 칸토어 집합 문제에 접근하는 데 힌트를 주었다. 병합 정렬은 리스트를 중앙을 기준으로 전반부와 후반부로 나누어 각각 계속 정렬을 한 후에, 다시 전반부와 후반부를 합치면서 다시 한 번 정렬하는 방식이다. 여기서 영감을 얻은 것은 전반부와 후반부를 나누어 각각 정렬한다는 것이다. 마치 칸토어 집합 문제에서 스트링을 3등분으로 나누고, 첫 번째 덩어리를 다시 또 3등분으로 나누고, 또 다시 그 첫 번째 덩어리를 나누고... 내 머릿속에서 이해된 논리를 글로 설명하지 못하여 답답하지만, 요점은 3등분하고 그중 첫 번째와 세 번째 덩어리를 마치 병합 정렬의 전반부와 후반부처럼 따로 다시 3등분하는 과정을 반복한다는 것이다. 이에, 아래 코드에서 left, right로 나누어 재귀 함수를 사용했음을 확인할 수 있다.

 

** 참고로 병합 정렬 문제는 아래 링크에서 확인할 수 있다.

24060번: 알고리즘 수업 - 병합 정렬 1

 

 

3. 정답 코드

• sys.stdin.readliens() : 입력이 끝날 때까지 여러 줄의 입력을 받음

import sys

def recursive(data) :
    length = len(data) // 3
    if length < 1 :
        return data
    left = recursive(data[:length])
    middle = ' ' * length
    right = recursive(data[length*2 : ])

    return left + middle + right

# main
numbers = sys.stdin.readlines()
for n in numbers :
    n = int(n)

    data = '-' * (3 ** n)
    answer = recursive(data)
    print(answer)

"파일의 끝에서 입력을 멈춘다." 이것 때문에 sys 모듈을 가져오고, stdin.readlines()를 사용해야 한다.

 

 

4. 기타

 재귀 함수가 익숙하지 않았기 때문에 테스트 코드를 군데군데 적으며 값을 트래킹했다. 출력된 테스트 코드를 보면, 머릿속으로만 이해했던 재귀의 원리를 다시 한 번 확실하게 인지할 수 있었다. 재귀의 작동 방식을 알아도, 머리로만 값을 생각하다보면 자꾸 길을 잃었기 때문이다.

 

 재귀 함수의 종료 조건에서 처음엔 아무 생각없이 return만 적었었다. 즉, 리턴 값이 None이기 때문에 return left(=None) + middle(=str) + right(None) 부분에서 프로그램이 비정상적으로 종료됐었다. 따라서 '-'인 data를 반환하도록 수정하였다.