print_star (1)

2017-10-19

algorithms, star

백준 온라인 저지에는 다양한 알고리즘 문제들이 많이 있다.

그 중에서 별찍기-11 (2448번) 문제에 대해 포스팅하려고 한다.

해당 포스팅 내용으로 저작권 문제가 발생할 경우 글을 삭제하도록 하겠습니다. :)

이 포스팅은 누구에게 보여주기가 아닌 내가 그냥 정리하는 수준이므로 소스코드가 자세하게 나와있지 않다.

참고하기 바란다.

문제

문제는 다음과 같다.

입력: 첫째 줄에 N이 주어진다. N은 항상 3*2^k 수이다. (3, 6, 12, 24, 48, …) (k <= 10)
출력: 첫째 줄부터 N번째 줄까지 별을 출력한다.

만약 24를 입력했다면 다음과 같은 별들이 이쁘게 찍힌다.

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

첫 번째 알고리즘

맨 처음 이 문제를 보고 어떻게 구현할지 고민하다가
번뜩 떠오른게 바로 이진트리 였다.

아래 모양을 하나의 노드로 보고

1
2
3

  *  
 * *
*****

좌측, 우측 노드를 연결해 나가면 저런 모양이 만들어 지겠구나! 라고 생각하며 유레카! 를 외쳤다.

먼저 트리형태로 저장할 StarNode 클래스와 별의 시작 좌표값을 저장할 Coordinate 클래스를 만들었다.

class StarNode implements Cloneable {
   Coordinate startCordinate;
   StarNode left;
   StarNode right;
   ...
 }

class Coordinate {
   public int x;
   public int y;
   ...
}

StarNode 클래스는 좌측, 우측 자식노드를 생성할 때 자기 자신을 복제해서 갖다 붙히려고 Cloneable 인터페이스를 구현했다.

물론 clone 할때 재귀적으로 내부의 모든 노드들을 복사해줘야 하는 문제가 있어서 귀찮긴 했다.

그럴땐 재귀 재귀 재귀…!!!! (훗날 커다란 성능이슈가…)

일단 전체적인 알고리즘을 서술하면 다음과 같다.

Input으로 N 값을 입력받고, N을 통해서 k의 값을 알아낸다. (코드상의 k는 0부터 시작하기로 정했다)
k를 통해 별 그림을 저장할 2차원 char 배열의 가로 길이를 생성한다. (6*2^k) - 1 이 되며 편의상 row라고 부르자.
input과 row를 통해 2차원 char 배열을 초기화 한다. char[][] canvas = new char[input][row] 가 되겠다.
이진트리의 root 노드를 생성한다. 이 노드가 저장할 좌표(coordinate)는 가장 위의 별 좌표이므로 (row / 2, 0) 이 된다.
이제 root노드를 이용해서 k번 루프를 돌면서 자식 노드들을 생성한다.
자식 노드는 root를 그대로 복사해서 root의 가장 왼쪽 리프노드와 가장 오른쪽 리프노드로 붙혀주면 된다. 이걸 k번 반복하면 이쁜 이진트리가 생성된다.
이진트리가 모두 생성됬으면 root 노드의 coordinate값을 이용해서 모든 자식노드의 coordinate를 생성한다.
coordinate는 좌측 자식노드는 부모 coordinate 값이 (x - 3, x + 3)으로, 우측의 경우는 (x + 3, y + 3)이 된다.
각 트리를 순회하면서 coordinate 값을 통해 위에서 만든 canvas 2차원 배열에 * 모양들을 찍는다. 다시 말하지만 coordinate는 별이 그려질 시작 좌표만을 저장하고 있는 값이다.
자 이제 끝났다. 출력을 해보자.

오… 별모양이 위에 그림들처럼 이쁘게 잘 찍힌다.

물론 처음 소스코드 작성했다고 바로 결과가 나오진 않았고…

여러번 손을 봤다. ;)

첫 번째 알고리즘 완료!

이제 다 만들어진 소스코드를 백준 온라인 저지에 제출해보자!

그 결과…!!!!

재귀를 남발한 그 결과…!!!

시간초과!!!!

아… ㅋㅋㅋㅋㅋㅋ

input이 200이 되는 순간…. 응답이 없다… 넘 느리다… 아… ㅋㅋㅋㅋㅋㅋ

재귀를 모두 loop로 바꿔봐야겠다.

라고 생각 했으나

새로운 알고리즘을 생각해보기로 결정했다.

Dev Huna

Algorithms

print_star (1)

문제

첫 번째 알고리즘

첫 번째 알고리즘 완료!