2447_별찍기 -10

문제는 더보기!

 

문제

재귀적인 패턴으로 별을 찍어 보자. 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 복사

27

예제 출력 1 복사

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

재귀함수에서 가장 중요한건 규칙을 발견하는 일 같다. 

 

# 111
# 101
# 111
#
# 111111111
# 101101101
# 111111111
# 111000111
# 101000101
# 111000111
# 111111111
# 101101101
# 111111111

그래서 문제를 보고 어느정도 출력될 결과를 예상해서 적어보았다. 그니까 가로 세로는 3배씩 되며, 첫번째는 옆으로 똑같이 3개를 반복출력하고, 중간줄에서는 가운데 빈칸을 만들어주고, 마지막에는 또 3배씩 똑같이 출력하면 되겠구나.. 하고 생각하고 코드를 짜 보았다.

 

def f(lst,N):
    if N==1:  #탈출 조건
        for _ in range(len(lst)):
            for k in range(len(lst[_])):
                print(lst[_][k], end='')
            print('')
        return

    new_lst=[[]]*(3*len(lst))
    l = len(lst)
    for i in range(len(new_lst)):
        if 2 * l > i >= l:
            new_lst[i] = lst[i%l]+[' ']* l+lst[i%l]
        else :
            new_lst[i] = lst[i % l] + lst[i % l] + lst[i % l]

    return f(new_lst,N-1)

first_lst =[['*','*','*'],['*',' ','*'],['*','*','*']]
N = int(int(input())**(1/3))
f(first_lst,N)

#메모리 초과

# 111
# 101
# 111
#
# 111111111
# 101101101
# 111111111
# 111000111
# 101000101
# 111000111
# 111111111
# 101101101
# 111111111

리스트를 하나 만들어서 출력될 조건을 넣고, 작은리스트에서 큰 리스트가 되게끔 만들어 나가는 구조로 만들었다.

(사실 이럴꺼면 while문이나 for문쓰는거랑 똑같긴 하다..)

 

아무튼 만들어서 결과는 제대로 나왔는데 메모리 초과가 났다 ㅠㅠ 어떻게하면 공간복잡도를 줄일 수 있을까 고민하다 보니 굳이 배열을 삼중까지 안써도 된다는 생각이 들었다.

 

쉽게 설명하자면 [ [ '*','*','*'],['*',' ','*'],['*','*','*']] 이처럼 되어있는 배열을 굳이 쓸필요없이 문자열로

["***","* *","***"] 이렇게 간단한 이중배열로 만들면 되는 문제였다.

 

문제 푸는 방법에만 너무 집중했던 것 같다 ㅠㅠ 그래도 성공!

 

def append_star(len):
    if len == 1:
        return ['*']

    Stars = append_star(len//3)
    lst = []

    for s in Stars:
        lst.append(s *3)
    for s in Stars:
        lst.append(s + ' '*(len//3) + s)
    for s in Stars:
        lst.append(s *3)


    return lst

n=int(input())
print('\n'.join(append_star(n)))