print_star (2)

2017-10-19

algorithms, star

지난번 작성한 포스팅에 이어서 새로운 알고리즘으로 문제를 풀어보기로 했다.

지난번 내용이 궁금하면 여기를 통해 확인하기 바란다.

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

이 포스팅은 누구에게 보여주기가 아닌 내가 그냥 정리하는 수준이므로 소스코드가

자세하게 나와있지 않다. 고 이전 포스팅에도 말했었다.
참고하기 바란다. ;)

자 그럼 이번에는 이진 트리가 아닌 동적 프로그래밍 기법을 통해서 문제를 풀어보자.

문제

문제는 다음과 같다.

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

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

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

유레카!

위 그림을 자세히 보면

1
2
3

  *  
 * *
*****

이런 별모양이 계속 반복해서 나타난다는 것을 알 수 있다.

바로 이거다! 동적 프로그래밍!! Dynamic Programming!!!!!!

커다란 별모양을 잘 살펴봤더니 작은 별모양들이 보인다!

작은 별모양을 하나씩 만들어서 저장 해놓고

필요할때 저장된 별모양을 꺼내서 사용하면 이게 바로 동적 프로그래밍!! Dynamic Programming!!!!!!

너무 오바했다.

아무튼 저런 방식으로 구현을 해볼까 한다.

풀이

이번에도 Coordinate 클래스가 필요하다.

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

이 클래스는 오늘도 별모양을 만들 시작 좌표를 저장할 클래스이다.

이 클래스에는 left, right 라는 메소드가 있는데 k의 값을 기준으로 x, y 좌표가 얼마씩 증가될 것인지를 생성해낸다.

left일 경우는 왼쪽 별을 그릴때, right의 경우는 오른쪽 별을 그릴때가 되겠다.

예를 그림으로 한번 보면

k = 1 일 경우 N은 6이 되므로 다음과 같은 별모양이 찍혀야 한다.

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

위 별모양을 만들기 위해 아래 별모양의 모든 좌표들을 (x - 3, y + 3) 로 똑같이 복사하면

1
2
3

  *  
 * *
*****

아래와 같은 별모양이 된다.

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

오! 그럼 (x + 3, y + 3)으로도 복사하면!!!

다음과 같이 우리가 원하는 별모양이 완성된다.

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

이게 k = 1일 경우이다.

만약 k = 2일 경우 위의 별들의 좌표를 전부 (x - 6, y + 6)과 (x + 6, y + 6) 만큼 복사해주면

아래와 같이 N이 12일 경우의 별모양이 찍히게 된다.

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

k = 3일 경우 위의 별모양을 (x - 12, y + 12), (x + 12, y + 12) 위치로 각각 복사해주면 N이 24일 경우의 별모양이 나온다.

이 그림은 본 포스트 맨 위에 문제 설명부분을 참고하면 되겠다.

자 그럼 전체적인 알고리즘을 알아보자.

N을 입력 받는다. 이 N을 통해서 k의 값을 생성해낸다.
별들의 시작 좌표를 저장할 Coordinate[] coordinateSet 배열을 생성한다. 배열의 크기는 별 6개짜리 젤 작은 별들 전체의 개수가 저장될 것이다. 그 값은 k = 0일 경우 1, k > 0 일 경우 3 * 3^(k - 1) 이 된다.
전체 별모양을 저장할 2차원 char 배열을 생성한다. x좌표 전체의 크기 (totalWidth라고 하자)인 (6 * 2^k) - 1이 된다. 즉, char[][] canvas = new char[N][totalWidth] 가 된다.
맨 처음 제일 꼭대기에 있는 별의 좌표를 알아낸다. (totalWidth / 2, 0)이 된다.
이 값을 coordinateSet[0]에 넣어준다. 이제 시작!!
맨 초기에는 coordinateSet에 값이 1개뿐이 없으므로 pointer를 1로 지정해준다. 이 pointer는 앞으로 새로운 별들이 복사될 위치를 기억하게 될 것이다.
이제 loop를 돌자. 0부터 k 전까지 쭉 돌자. 왜냐면 우리는 k번만큼 별을 복사하면 되기 때문이다.
왼쪽 오른쪽으로 별들을 복사해야 한다. 이걸 판단하려면 loop 처음에 pointer를 임시 변수에 저장해야한다. pointer 변수는 loop를 돌면서 변경되기 때문이다. 복사된 변수는 loopCount라고 해보자.
0부터 loopCount 전까지 루프를 돌면 지금까지 coordinateSet에 저장된, 즉 k - 1번째까지 생성된 coordinate들에 접근할 수 있다. 이 값들을 coordinateSet[pointer++]에다가 복사될 위치를 계산해서 저장해주면 왼쪽, 오른쪽 별그림들을 모두 복사할 수 있다.
coordinateSet을 모두 순회하면서 coordinate 값을 통해 별을 canvas[][] 변수에 그려준다.
출력하면 이쁘게 별들이 나온다.

말로만 설명하려니 하는 나도 답답하고 보는 사람은 더 죽을맛일 것이다. ~~(이게 무슨 멍멍이소리야! 이럴 지도…)~~

4번부터 9번까지 소스코드를 첨부하면 다음과 같다.

Coordinate startCoordinate = new Coordinate(totalWidth / 2, 0);
coordinateSet[0] = startCoordinate;
int pointer = 1;

for (int i = 0; i < level; i++) {
  int loopCount = pointer;
  for (int j = 0; j < loopCount; j++) {
    coordinateSet[pointer++] = coordinateSet[j].left(i);
  }
  for (int j = 0; j < loopCount; j++) {
    coordinateSet[pointer++] = coordinateSet[j].right(i);
  }
}

coordinateSet[j].left(i), coordinateSet[j].right(i) 는 무엇이냐!

다음과 같다.

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

  public Coordinate left(int level) {
    int increment = (int)(3 * Math.pow(2, level));
    return new Coordinate(this.x - increment, this.y + increment);
  }

  public Coordinate right(int level) {
    int increment = (int)(3 * Math.pow(2, level));
    return new Coordinate(this.x + increment, this.y + increment);
  }
}

이 부분은 k에 따라 얼만큼 위치로 별들을 복사할지 설정하는 메소드이다.

자 이제 별들의 시작 좌표가 coordinateSet이라는 배열에 모두 저장되었다.

이 배열을 순회하면서 canvas 변수에 실제 별들의 위치에 * 을 그려주면 된다.

마지막으로 한가지 팁!

별을 출력할때 매번 System.out.println()을 이용해서 출력하면 굉~~~~~장한 성능 저하가 발생한다.

System.out.println()이 호출될때 마다 Java application이 block되므로 가능한 적게 호출하도록 해보자.

나는 canvas에 저장된 char 값들을 모두 StringBuilder에 append()해서 한방에 System.out.println()으로 출력했다.

(사실 이렇게 안하고 건건히 System.out.println()으로 했다가 시간 초과로 틀렸었다…)

그럼 즐거운 코딩 하세요~

Dev Huna

Algorithms

print_star (2)

문제

유레카!

풀이