[Baekjoon] 2448. 별찍기 - 11

문제 설명

문제

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

입력

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, …) (0 ≤ k ≤ 10, k는 정수)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력 1

24

예제 출력 1

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

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 재귀

문제 풀이

# Recursive

재귀 함수를 이용하는 별찍기 문제입니다.

풀이 과정

문제를 보고 규칙성을 찾아 재귀 함수로 구현해야 하는 문제입니다.

n=3일 때 일정한 패턴의 삼각형 모양이 찍히는 것을 알 수 있습니다. 이를 바탕으로 n=3일 때는 출력(구현 시에는 인덱싱)을 하고, n > 3 일때는 재귀 함수를 호출합니다.

재귀 함수를 이용할 때는 어떤 파라미터를 규칙적으로 전달해줄 것인지가 중요한데, 저는 이를 위해 3가지 파라미터(시작 행, 시작 열, 삼각형 크기)를 사용했습니다.

전체 코드

전체 코드입니다.

빈 문자열이 포함된 empty_list 를 전달해주고, 적절한 위치에 star가 들어간 star_list를 반환받도록 구현했습니다.

마지막 출력 부분에서 리스트를 문자열로 바꿔주고 sys.stdout.write를 사용해 한 번에 출력해주었는데, 이는 시간초과를 극복하기 위함입니다.

출력해야 할 것이 많다보니 일반적인 print 문을 사용하여 리스트로 출력하면 시간초과가 발생합니다.

import sys

def make_star_list(i, j, n, star_list):
    if n == 3:
        star_list[i][j] = '*'
        star_list[i+1][j-1] = '*'
        star_list[i+1][j+1] = '*'
        for col in range(j-2, j+3):
            star_list[i+2][col] = '*'
    else:
        star_list = make_star_list(i, j, n//2, star_list)
        star_list = make_star_list(i+n//2, j-n//2, n//2, star_list)
        star_list = make_star_list(i+n//2, j+n//2, n//2, star_list)
    return star_list

N = int(input())
empty_list = [[' ' for _ in range(2*N-1)] for _ in range(N)]
star_list = make_star_list(0, N-1, N, empty_list)
star_string = '\n'.join([''.join(row) for row in star_list])
sys.stdout.write(star_string)

배운 점

• Top-down의 재귀를 이용할 때는 base case와 general case를 먼저 찾는다.
• 재귀 함수를 구현할 때는 어떤 파라미터를 규칙적으로 전달할 것인지 생각한다.
• 리스트의 원소에 출력할 것이 많다면, 리스트를 문자열로 바꾸고 sys.stdout.write로 한 번에 출력하면 시간을 줄일 수 있다.