사용 언어: python 3.9.5

❓ Problem

문제 설명

문제

https://www.acmicpc.net/problem/2447

별 찍기 - 10

재귀적인 패턴으로 별을 찍어 보자.

입력

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

출력

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

🚩 Solution

1. 접근법

2차원 리스트를 기본값 ' '(공백)으로 만들어두고,,, 분할정복으로 하나씩 훑어간다.

구역은 9 구역으로 나눈다.

1 2 3

4 5 6

7 8 9

각 구역은 가운데 부분과 나머지 부분으로 나뉜다.

기저:

크기가 1이다.

가운데 부분: 공백으로 가만히 냅둔다.

solve():

# 5 부분 처리 (아무것도 안 하면 됨)

# 나머지 부분: 재귀

2. 코드

global arr

def solve(size: int, x: int, y: int) -> None:
    global arr

    if size == 1:
        arr[x][y] = '*'
        return
    
    next_size = int(size/3)

    solve(next_size, x, y);
    solve(next_size, x + next_size, y);
    solve(next_size, x + next_size * 2, y);

    solve(next_size, x, y + next_size);
    solve(next_size, x + next_size * 2, y + next_size);

    solve(next_size, x, y + next_size * 2);
    solve(next_size, x + next_size, y + next_size * 2);
    solve(next_size, x + next_size * 2, y + next_size * 2);

import sys
input = sys.stdin.readline

N = int(input())
# 출력 결과의 틀을 만들어둔다.
arr = [[' ' for j in range(N)] for i in range(N)] # 바깥 for문을 뒤에
solve(N, 0, 0)

for i in arr:
    for j in i:
        print(j, end='')
    print()

3. 결과

채점 결과

correct

메모리
67608 KB

시간
2712 ms

시간 복잡도 분석

가운데 부분 빼고 모든 판을 읽어야 하므로 O(n^2)

📕 피드백

1. 검색한 내용

2차원 리스트 만들기

rr = [[' ' for j in range(N)] for i in range(N)] # 바깥 for문을 뒤에

2차원 리스트 출력

for i in arr: # i는 1차원 리스트
    for j in i:
        print(j, end='')
    print()

2. 실수

3. 발전 방향

재귀를 풀 때는 함수의 리턴값 모양을 만들어두자.
예시: 1차원 리스트 안에 문자열만 있는 형태로 만들기
-> 이런 식으로 형태가 고정적이어야 재귀 함수에서 활용 가능

<고수의 풀이>

한 블럭을 재귀로 만들고, 이 블럭을 복사하는 방법으로 만들었다.

즉, 나처럼 재귀를 8번 돌지 않고 1번만 돌아서 더 효율적이다.

결과를 1차원 리스트에 담았다.

리스트에는 문자열이 들어 있으며, 한 문자열은 한 줄이 된다.

이렇게 해서 출력이 용이하게 한다.

# https://www.acmicpc.net/source/28199391

def concatenate(r1, r2):
    return [''.join(x) for x in zip(r1, r2, r1)]

def star10(n):
    if n == 1:
        return ['*']
    n //= 3
    x = star10(n)
    a = concatenate(x, x)
    b = concatenate(x, [' ' * n] * n)

    return a + b + a

print('\n'.join(star10(int(input()))))

<도토리 풀이>

고수풀이랑 접근법은 같다.

근데 블럭을 복사하는 방법이 좀 더 인간친화적이라 읽고 이해하기 편하다.

고수는 블럭을 요소를 zip으로 분해한 뒤 다시 합친다.

도토리는 블럭 요소를 3배로 늘려준다.

def printStar(n):
    # 기저
    if n == 3:
        return ['***','* *','***']

    results = []
    before_star = printStar(n//3) # 이전 별 모양

    # 위, 아래 패턴. 둘은 같은 모양이다.
    top_bottom = []
    for i in range(n//3):
        text = before_star[i]*3
        top_bottom.append(text)

    # 중간 패턴
    middle = []
    for i in range(n//3):
        text = before_star[i]+ ' '*(n//3) + before_star[i]
        middle.append(text)

    results.extend(top_bottom)
    results.extend(middle)
    results.extend(top_bottom)

    return results

import sys

n = int(sys.stdin.readline())
answer = printStar(n)

print('\n'.join(answer))

4. 느낀점

이 문제는 실버1인데 너무 쉬웠다.

라고 생각했으나...

고수의 풀이를 보니 좀 더 효율적인 코드로 만든다면 실버1일만 하다.