백준 2447 [python]

백준 2447

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

내 풀이

1. 반복문을 사용하여 각 행에 대하여 함수를 실행시킨다. 

2. 각 행을 idx로 가정하고 인덱스가 특정 범위에 들어간다면 공백으로 만든다.
   Ex) 문자열의 크기가 3이라면 idx가 1일 때, 공백으로 만들어준다.
       문자열의 크기가 9라면 idx가 3 ~ 5 범위일 때 공백으로 만들어준다. 

3. idx 값을 분할될 크기로 나눈 나머지를 idx에 저장한다. 
   -> 문자열을 3등분할 건데 잘라긴 길이에 맞는 idx를 설정

4. 이후 행을 3등분하여 재귀호출을 수행한다. (문제축소) 
   -> left, mid, right 3등분하여 재귀 호출 수행 
   -> 문자열이 공백 혹은 공백 묶음인 경우 재귀호출되지 않는다. ('*'로 이루어진 경우에 대해서만 재귀호출)
   문자열 길이가 1이 되면 함수를 종료한다. (종료조건)

5. 반환된 문자열들을 더하여 하나의 문자열로 만들어준다. 

코드

import sys 

def star10(data, idx) :

    N = len(data)

    # 종료조건 
    if N == 1 :
        return data

    l = N // 3
    r = l * 2

    mid = '*' * l

    # 특정 범위에 해당된다면 중앙을 
    if idx >= l and idx < r :
        mid = ' ' * l

    idx %= l

    # 문제 축소 
    left = star10(data[:l], idx)
    if mid != ' ' * l  :
        mid = star10(data[l:r], idx) 
    right = star10(data[r:], idx)

    return left + mid + right

N = int(sys.stdin.readline().rstrip())

for i in range(N) :
    print(star10("*"* N, i))

결과

마무리

1. 재귀 문제에 익숙하지 않아서 그런지 패턴을 찾는데 오래 걸렸다.
   다른 문제들의 경우 풀리지 않으면 답을 보곤했지만 재귀의 경우 재귀적인 규칙을 찾는 훈련을 해야하기 때문에 답을 보지 않았다. 

2. 재귀의 핵심은 [종료조건]과 [문제축소] 부분을 찾는 것이다.
   이를 떠올리는데 오래 걸렸으나 알고난 후 그리 오래 걸리지 않았다.

3. idx %= 3을 수행하여 해결되지 않았었다. 
   이는 줄어든 문자열의 길이를 고려하지 않은 잘못된 접근이었다.
   앞으로는 어떤 코드 작성하거나 특정 값을 사용하더라도 왜 사용했는지 생각해봐야겠다.