백준 온라인 저지 2447번 문제로, 프랙탈 도형처럼 작은 단위로 내려가면서 동일한 패턴이 반복되는 도형을 스케일에 따라서 출력하는 문제이다.
https://www.acmicpc.net/problem/2447
N=1 일 때 3×3의 기본 패턴을 출력한다. 이후 N이 커질 때마다 가로 세로가 각각 3배씩 커지면서 현재 패턴을 9번 반복하는 식이다. 기본적으로 재귀를 쓰겠지만, 접근방법은 사실 다양하다. 2차원 배열 혹은 1차원배열로 버퍼를 만들고 규칙에 따라 '*' 혹은 ' '를 채워넣고 이를 나중에 문자열의 형태로 출력하는 방법도 있을 것이다. (이런 풀이가 많은 것 같다.)
파이썬에서 문자열은 immutable(불변) 데이터 타입이다. 이 말은 문자열 객체는 리스트와 달리, 한 번 생성된 이후에는 그속의 개별 문자를 변경할 수 없다는 말이다. 따라서 리스트를 만들어서 비슷하게 채워넣고 이를 join 하는 방법이 있을 수 있다. 하지만 개인적으로는 이 문제에서는 이 방법이 그다지 효율적이지 못하다. N 회의 시행에서 가로 세로를 3등분한 9개의 조각에 대해 재귀 호출을 반복해야 하기 때문에 시간복잡도가 지수적이라는 문제가 있다. (물론 실질적으로 6단계 이상 부터는 화면에 찍을 수 있을까 싶지만…)
대신에 출력될 각 라인을 연결한 리스트를 리턴하는 함수를 작성하는 것으로 해보자. 이를 통해서 기본 패턴에 대해서 *이 출력될 위치에는 이전 레벨의 전체 데이터를, 공백이 출력될 위치에는 이전 레벨의 공백 데이터를 가져와서 라인단위로 조립하면 된다.
먼저, 채워져야 할 타일과 공백 타일의 기본 패턴은 다음과 같이 정의한다.
tile = ['***', '* *', '***']
spc = [' '] * 3간단하게 공백이 되는 부분을 만들어주는 함수를 보자.
from typing import List
def space(n: int) -> List(str):
if n < 2:
return spc
xs = space(n - 1)
# xs는 이전 단계의 공백 사각형으로 3^(n-1)개 원소를 갖는 리스트
res: List[str] = []
for _ in spc
temp: List[List[str]] = [xs] * 3
for i in range(len(xs)):
res.append(''.join(temp[j][i] for j in range(3)))
return res제대로 동작하는지 살펴보려면, spc 패턴의 내용을 공백이 아닌 "###" 등으로 바꿔서 확인해본다.
print('\n'.join(space(2)))이번에는 채워지는 칸을 표현할 fill() 함수를 구현할 차례이다. space() 함수에서 기본적인 구조가 모두 마련돼 있으므로 약간의 변형을 더하면 된다.
- 이전 단계의
fill()과space()를 모두 호출해서 필요한 요소들을 준비한다. - 기본패턴의
*에 대해서는fill()의 결과를, 공백에 대해서는space()의 결과를 사용한다.
def fill(n: int) -> List[str]:
if n < 2:
return tile
xs = fill(n - 1)
ys = space(n - 1)
res: List[str] = []
for row in tile:
temp: List[List[str]]
temp = [xs if c == '*' else ys for c in row]
for i in range(len(xs)):
res.append(''.join(temp[j][i] for j in range(3)))
return res마찬가지로 테스트해보자. 사실 여기까지가 풀이의 끝이라 할 수 있다.
print('\n'.join(space(2)))문제에서는 레벨이 아닌 도형의 크기를 입력받는다, 즉 27을 입력받으면 fill(3)의 결과를 출력하도록 한다. 입력의 범위가 제한되어 있으므로 사전을 만들어서 처리하면 되겠다.
ns = {n**3:n for n in range(1, 10)}
print('\n'.join(fill(ns[int(input())])))