[Silver IV] 별 찍기 - 19 - 10994

문제 링크

성능 요약

메모리: 32000 KB, 시간: 128 ms

분류

구현, 재귀

문제 설명

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 차례대로 별을 출력한다.

---

풀이

우선 n=4일때 결과에 대해 보면 아래와 같다

*************
*           *
* ********* *
* *       * *
* * ***** * *
* * *   * * *
* * * * * * *
* * *   * * *
* * ***** * *
* *       * *
* ********* *
*           *
*************

이를 유심히 들여다보니 아래 두 규칙이 합쳐진 형태이다

1. *************
   
     *********  
   
       *****    
   
         *      
   
       *****    
   
     *********  
   
   *************

2. 1을 90도 회전한 모양
   
   

이 두 규칙을 합치는 코드이며, 값을 저장하기 위해 배열을 이용하였다.
규칙에 대한 점화식은 outside변수에 있는대로 $4(n-1) + 1$이며, 절반의 코드만 작성 한 뒤 180도 회전한 곳에 똑같이 찍어주는 방식을 사용하여 시간복잡도를 절반으로 줄였다.

아이디어

코드

n = int(input())
outside = (n-1)* 4 + 1
graph = [[' ' for _ in range(outside)] for __ in range(outside)]
k = 0
for i in range(outside//2 + 1):
    if i % 2 != 0:
        continue

    for j in range(k, len(graph)-k):
        graph[i][j] = '*'
        graph[outside-i - 1][j] = '*'
        graph[j][i] = '*'
        graph[j][outside-i-1] = '*'

    k += 2

for i in range(len(graph)):
    # print(graph[i])
    for j in range(len(graph[i])):
        print(graph[i][j], end='')
    print()

---

회고

처음 봤을 때 규칙이 잘 보이지 않아 어려웠는데 한번 규칙을 생각해내니 간단한 문제였다.
오랜만에 풀어본 별찍기 문제라 재미있었지만, 앞으로 시간 단축은 필수라고 느꼈다.

또한 풀이하면서 코드가 깔끔하게 나와 기분이 매우 좋았다.
리스트 컴프리헨션을 이용하여 출력 부분을 조금 더 깔끔하게 바꿀 수 있으면 가독성이 더욱 올라갈 듯 싶다.