[알고리즘][파이썬] 백준_2447번_별 찍기 - 10

***
* *
***

 

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다(N은 3, 9, 27…).

재귀함수를 이용해 문제를 해결한다.

---

1차 시도

# 재귀함수 이용(결과: 출력 형식이 잘못되었습니다)

def star(N):
    if N == 1:
        return ['*']

    lst = []
    patt = N // 3

    for i in star(patt):
        lst.append(i * 3)
    for i in star(patt):
        lst.append(i + ' ' + i) # ' '에 (patt)를 곱해 주어야 한다.
    for i in star(patt):
        lst.append(i * 3)
    return lst

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

 

[그림1] 가운데 공백 표현에 문제가 있다.

[그림1]은 첫 번째 시도에서 9를 입력(백준 예제는 27을 입력으로 다룬다)하였을 때 출력 결과이다.

가운데 여백이 가로 3칸으로 표현되어야 하는데 1칸으로만 표현되었다.

따라서 ' '에 * (N // 3)이 곱해져야 한다.

---

2차 시도

# N // 3을 ' '에 곱함(결과: 맞았습니다!)

def star(N):

    if N == 1:
        return ['*']
    
    lst = []
    patt = N // 3

    for i in star(patt): # 1번 for문
        lst.append(i * 3)
    for i in star(patt): # 2번 for문
        lst.append(i + ' ' * (patt) + i)
    for i in star(patt): # 3번 for문
        lst.append(i * 3)
    
    return lst

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

[그림2] 가운데 공백이 잘 표현되었다.

 

N/3의 패턴이기 때문에 입력 값이 9인 경우 9/3=3이기 때문에 [그림2]와 같이 가운데 공백은 3칸이 된다.

패턴 변수(patt)에 N / 3이 아닌 N // 3을 대입한 이유는 몫(정수 값)이 필요했기 때문이다.

---

해결한 방법

재귀함수를 이용해 해결하였다.

재귀함수는 마지막에 호출된 함수가 먼저 연산되어 결과 값을 직전 함수에 return하고 스택에서 사라지는데(Last In First Out), 이 점을 이용한다.

주의 할 점은 입력 값 정수 N이 1일때는 * 하나를 출력하는 조건을 주어야 하는데,

그렇지 않으면 Recursion Error가 발생한다.

 

코드 동작 방식을 이해하기 위해서 각 for문에 의해 추가된 리스트(lst) 값을 출력하였다.

['***'] # star(3)의 1번 for문
['***', '* *'] # star(3)의 2번 for문
['***', '* *', '***'] # star(3)의 3번 for문의 return 값

['*********'] # star(9)의 1번 for문, return된 star(3) 리스트의 0번 index의 값 연산 후 추가
['*********', '* ** ** *'] # star(9)의 1번 for문, return된 star(3) 리스트의 1번 index의 값 연산 후 추가
['*********', '* ** ** *', '*********'] # star(9)의 1번 for문, return된 star(3) 리스트의 2번 index의 값 연산 후 추가

['***'] # star(9)의 2번 for문, star(3)의 1번 for문
['***', '* *'] # star(9)의 2번 for문, star(3)의 2번 for문
['***', '* *', '***'] # star(9)의 2번 for문, star(3)의 3번 for문
['*********', '* ** ** *', '*********', '***   ***'] # star(9)의 2번 for문, star(3) 리스트의 0번 index의 값 연산 후 추가
['*********', '* ** ** *', '*********', '***   ***', '* *   * *'] # star(9)의 2번 for문, star(3) 리스트의 1번 index의 값 연산 후 추가
['*********', '* ** ** *', '*********', '***   ***', '* *   * *', '***   ***'] # star(9)의 2번 for문, star(3) 리스트의 2번 index의 값 연산 후 추가

['***'] # star(9)의 3번 for문, star(3)의 1번 for문
['***', '* *'] # star(9)의 3번 for문, star(3)의 2번 for문
['***', '* *', '***'] # star(9)의 3번 for문, star(3)의 3번 for문
['*********', '* ** ** *', '*********', '***   ***', '* *   * *', '***   ***', '*********'] # star(9)의 3번 for문, star(3) 리스트의 0번 index의 값 연산 후 추가
['*********', '* ** ** *', '*********', '***   ***', '* *   * *', '***   ***', '*********', '* ** ** *'] # star(9)의 3번 for문, star(3) 리스트의 1번 index의 값 연산 후 추가
['*********', '* ** ** *', '*********', '***   ***', '* *   * *', '***   ***', '*********', '* ** ** *', '*********'] # star(9)의 3번 for문, star(3) 리스트의 2번 index의 값 연산 후 추가

 

최종적으로 생성된 리스트,

['*********', '* ** ** *', '*********', '***   ***', '* *   * *', '***   ***', '*********', '* ** ** *', '*********']

join을 이용해 결합하면,

[그림2]와 같은 결과가 출력된다.