[구현] 백준 16505 (python)

 

몇 달 전에 풀었을 때는 못 풀었는데 오늘은 이상하게 풀렸다;

전에는 너무 어렵게 생각했던 것 같고 이번에는 전에 어디선가 이런비슷한 논리의? 문제를 풀었던 것 같아서

 

재귀함수 돌면서 배열에 추가해주면 된다고 생각했다.

(다행히 맞았음^^)

 

 

1) stars = [['*']]로 먼저 2차원 배열이 있다고 하자

 

2) 함수는 하나 만드는데 받아온 2차원 배열을 가지고 가공해서 오른쪽과 아래에 똑같은 배열을 붙인다(?라고 해야하나..)

- [['*']]를 받아왔다면 -> [['*', '*'], ['*']]

- [['*', '*'], ['*']] 를 받아왔다면 -> [['*', '*', '*', '*'], ['*', ' ', '*', ' '], ['*', '*'], ['*']]

=>재귀함수!

 

3) 위의 함수를 재귀함수로 만들어준다. (재귀 탈출문도 당근 있어야)

 

 

 

주의할 점
1)
beforeStars = copy.deepcopy(arr)부분을 해 준 이유는 
beforeStars = arr를 하면 arr이 재귀함수를 거치면서 변경되는데 참조때문에 beforeStars에 영향을 준다는 것이었다. 
beforeStars는 변경되어서는 안되는 배열에라 따로 빼준것이었으므로 deepcopy를 사용해 2차원배열을 카피해줬음.
https://jjuke-brain.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%ED%95%A0%EB%8B%B9%EA%B3%BC-%EB%B3%B5%EC%82%AC-copy%EC%99%80-deepcopy

파이썬 리스트의 할당과 복사 (copy와 deepcopy)

 

2)

또한 ' '빈칸이 들어가줘야 하는데 이를 고려하지 않고 별을 추가만 하고 있었다.
그래서 ' '를 추가하기 위해 아래와 같이 for 문 안에 if 문을 넣어 별을 추가해주기 전에 빈칸이 있어야 할 갯수를 확인해 추가해주었음.

이렇게 하면 '각 줄 끝에는 필요없는 공백을 출력하지 않는다'라는 제한조건도 역시 만족할 수 있음

 

---

 

import copy
n = int(input())
stars = [["*"]]  # 2차배열로
cnt = 0
def makeStars(num, arr):
    global cnt
    if cnt == num:
        return
    beforeStars = copy.deepcopy(arr)
    for i in range(len(arr)):
        if len(arr[i]) < len(beforeStars[0]) :
            for j in range(len(beforeStars[0]) - len(arr[i])):
                arr[i].append(' ')
        arr[i]+=beforeStars[i]
        
    arr+=beforeStars
    cnt += 1
    makeStars(num, arr)
    
makeStars(n, stars)

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

 

 

 

---

 

또 다른 풀이로는 아래와 같은 풀이가 있다.

보통 재귀를 배울 때 원리와 같은 원리로 짠 코드인데 아래 블로그에서 C로 구현된 코드를 보고 힌트를 얻었다.

https://kingsubin.com/259

kingsubin

 

 

import math

n = int(input())
length = int(math.pow(2, n)) # pow의 결과는 float
map = [[' ' for _ in range(length)] for _ in range(length)]

def func(x, y, length):
    if (length == 1):
        map[x][y] = '*'
        return

    newLength = length // 2
    func(x, y, newLength)
    func(x, y + newLength, newLength)
    func(x + newLength, y, newLength)

func(0, 0, length)

for i in range(length):
    for j in range(length):
        if j == length - i:
            break
        else:
            print(map[i][j], end = '')

    print()

 

* 하지만 이렇게 하면 첫번째 풀이보다는 메모리를 많이 차지할 수 밖에 없다. 미리 length*length크기의 2차원배열을 만들어놓고 시작해서 그렇다.