[파이썬]10997:별 찍기 - 22

문제 링크

요약

• 문제 난이도: 3/10(실버 2)
• 문제 타입: 재귀
• 특이 사항: 낚시성 케이스 존재

---

개요

알고리즘 문제에서 가장 잘 알려진 형태인 별을 출력하는 문제입니다.

N번째에 출력할 형태는 N-1번째 출력을 포함하고 있는 재귀적인 형태의 구조입니다.

예를 들어, 밑의 사진처럼 N=3일 때의 출력은 N=2일 때의 출력을 가운데에 포함하고 있습니다.

N=3일때 N=2번쨰의 출력을 포함하고 있음

이전에 별 찍기와 연관된 문제를 푼 적이 있다면, 조금 응용하여 풀 수 있는 문제입니다.

---

문제 풀이

미리 정리해 놓고 가야 할 것

1. 해당 문제는 재귀적인 함수호출을 연습하기 위해 만들어진 문제입니다.
2. 출력의 사이즈는 다음과 같은 관계를 가집니다. 가로: 4 * N - 3, 세로: 4 * N - 1
3. N번째 출력은 N - 1번째의 출력을 중심으로 두고, 양옆으로 2만큼, 위아래로 2만큼 확장된 형태를 출력합니다.
4. 출력의 2번째 열에는, 공백이 존재하지 않습니다. 따라서 공백을 제거해야 합니다.(이 부분이 정답률을 떨어뜨리는 낚시성 케이스입니다.)

코드 구현

따라서, 구현해야 할 코드들은 다음과 같습니다.

1. 1 <= N <= 100을 만족하는 정수 N을 입력받는 코드
2. 입력받은 정수 N을 바탕으로 별을 출력하는 함수인 print_star를 구현합니다.
   2-1. N=1, N=2일 때는 정해진 형태의 별을 그대로 출력합니다.
   2-2. N >= 3일 때부터 print_star를 재귀적으로 호출합니다.
   2-3. print_star(N - 1)에서 양 옆으로 2만큼, 위아래로 2만큼 확장하는 함수 expand_space함수를 구현합니다.

코드

def expand_space(star_output: list) -> list:
    """주어진 규칙에 맞게 2차원 리스트를 확장합니다."""
    # 가로축의 공간을 확장합니다.
    for x in range(len(star_output)):
        star_output[x].insert(0, " ")
        star_output[x].insert(0, "*")
        star_output[x].append(" ")
        star_output[x].append("*")
    # 세로축의 공간을 확장합니다.
    star_output.insert(0, ["*"] + [" "] * (len(star_output[0]) - 1))
    star_output.insert(0, ["*"] * len(star_output[0]))
    star_output.append(["*"] + [" "] * (len(star_output[0]) - 2) + ["*"])
    star_output.append(["*"] * len(star_output[0]))
    return star_output


def print_star(x: int) -> list:
    """규칙에 맞추어 x에 해당하는 2중 리스트를 리턴합니다."""
    # 2-1. N이 1 또는 2일때는 정해진 포맷의 별을 리턴합니다.
    if x == 1:
        return [["*"]]
    elif x == 2:
        return [
            ["*", "*", "*", "*", "*"],
            ["*", " ", " ", " ", " "],
            ["*", " ", "*", "*", "*"],
            ["*", " ", "*", " ", "*"],
            ["*", " ", "*", " ", "*"],
            ["*", " ", " ", " ", "*"],
            ["*", "*", "*", "*", "*"],
        ]
    # 2-2. N >= 3일 경우, print_star를 재귀적으로 호출합니다.
    # print_star(N - 1)을 호출하여 N - 1일때의 출력을 호출합니다.
    prev_star_output: list = print_star(x - 1)
    # N - 1일 때의 출력에 위아래 2, 양 옆 2만큼 공간 확장
    prev_star_output = expand_space(prev_star_output)
    prev_star_output[2][-2] = "*"
    return prev_star_output


def main():
    # 1. 입력으로 1 <= N <=의 값을 입력받는다.
    N = int(input())
    # 2. 해당 N에 맞는 별이 담긴 리스트를 변수에 저장한다.
    star_list = print_star(N)
    # 2중 리스트에 담겨있는 별을 출력한다.
    for line in map("".join, star_list):
        print(line.rstrip())


if __name__ == "__main__":
    main()

코드 리뷰

• 가독성: 5/5(코드에 충분한 주석이 포함되어 있고, 직관적인 함수명을 사용함. black포매팅이 적용됨.)
• 효율성: 4/5(1 <= N <= 100안에서는 128ms의 시간이 걸림, 하지만 더 짧은 시간에 출력이 가능한 코드가 존재)

사실 이 문제는 재귀를 사용하지 않고, 패턴을 사용해 더 짧게 문제를 풀 수 있습니다. 하지만 가독성이 떨어지고, 이해하기 어려운 코드이기 때문에, 먼저 재귀적으로 풀어보고 생각해 보는 것을 추천드립니다.

다른 풀이(jh05013님의 풀이입니다.)

n = int(input())
print("*"*(4*n-3))
for i in range(n-1):
    print(("* "*(i+1)+" "*(4*n-4*i-5)+" *"*i).strip())
    print("* "*(i+1)+"*"*(4*n-4*i-5)+" *"*i)
if n != 1:
    print("* "*(2*n-1))
    print("* "*(2*n-1))
for i in range(n-1):
    print("* "*(n-1-i)+" "*(4*i+1)+" *"*(n-1-i))
    print("* "*(n-2-i)+"*"*(4*i+5)+" *"*(n-2-i))