[단계별로 풀어보기][python 3] 재귀 - 별찍기 - 10 (2447)

2447번: 별 찍기 - 10 (acmicpc.net)

2447번: 별 찍기 - 10

위와같은 패턴을 출력하는 문제다.

방안 1

각 빈칸은 다음과 같은 규칙이 존재한다.

x축과 y축의 값이 (n//3)%3 = 1 일 때 빈칸이 된다. (n은 3의 거듭제곱)

따라서 Boolean 배열을 이용해 빈칸을 구별한 뒤, 그에 따라 출력하면 된다.

def drawStar(a, m):
    if m<1:
        return a
    for y in range(n):
        for x in range(n):
            if ((y//m)%3 == 1) and ((x//m)%3 == 1):
                a[y][x] = False
    return drawStar(a, m//3)
    
n = int(input())

first = []
for x in range(n):
    first.append([True]*n)
done = drawStar(first, n)

for i in range(n):
    for j in range(n):
        if done[i][j] == True:
            print('*', end="")
        else:
            print(' ', end="")
    print("")

여기서 주의할 점은, first 배열을 선언할 때 [[True]*n]*n 을 하게 되면

[True]*n 이란 배열을 '참조하여' n개의 배열이 만들어지게 된다.

그렇게 되면 first[1][1] = False로 수정하면 모든 배열의 1번 인덱스가 바뀌므로 위의 방식을 사용해주자.

결과

시간복잡도가 O(n^2)라서 오래 걸린다. pypy3이 아니면 시간초과로 실패한다.

 

방안 2

처음부터 기본형인 배열 ['***', '* *', '***']을 만들어두고,

그 배열을 n번만큼 반복하여 array에 입력하는 방식을 취한다.

def star(n:int, x: list) -> list:
    array = []
    if n == 3:
        return x
    else:
        for i in x:
            array.append(i*3)
        for i in x:
            array.append(i+' '*len(i)+i)
        for i in x:
            array.append(i*3)
        return star(n//3, array)

n = int(input())
first = ["***", "* *", "***"]
final = star(n, first)
for i in final:
    print(i)

결과

시간복잡도가 O(n)으로 매우 빠른 시간내에 실행된다.