[알고리즘] 백준 - 2447 별 찍기 - 10 해설, node js 구현

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***

* *

***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

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

 

해설

이 문제는 그림을 그리면서 먼저 패턴을 파악하면 쉽게 풀 수 있을 것 같다.

입력값이 3 일때를 생각해보면

x	x	x
x		x
x	x	x

인데, 이 경우에 1,1이 공백을 출력해야 하는 위치인 것을 알 수 있고,

이 패턴이 반복되기 때문에 i, j의 1 % 3(1 나머지 3)의 값이 1인 곳은 공백으로 처리를 하면 첫번째 단계는 해결이 된다.

이 경우가 재귀에서 처리해는 최소범위의 값이다.

 

이 코드를 그래도 9로 넘어갈 경우

x	x	x	x	x	x	x	x	x
x		x	x		x	x		x
x	x	x	x	x	x	x	x	x
x	x	x	x	x	x	x	x	x
x		x	x		x	x		x
x	x	x	x	x	x	x	x	x
x	x	x	x	x	x	x	x	x
x		x	x		x	x		x
x	x	x	x	x	x	x	x	x

색칠된 부분이 정답과는 다른 부분이 된다.

즉, 첫번째 우리가 공백으로 처리한 부분 이외에 추가로 공백으로 처리해야하는 좌표는 아래와 같다.(좌표를 편의상 i, j로 작성합니다. for loop에서 자주 사용되는 변수입니다.)

 

(3,3) (3,4) (3,5)

(4,3) (4,4) (4,5)

(5,4) (5,4) (5,5)

 

여기서 i, j 의 범위는 모두

3^1 <= i,j < 3^1 + 3^1 이다.(^1은 1승, 제곱인 경우 ^2로 표현합니다.)

 

즉, 3^1부터 3^1 크기의 정 사각형이 빈 공백으로 표시가 된다.

 

입력값이 27이라면

3^2 부터 3^2+3^2까지 (9 ~ 17) 공백으로 표현이 된다.

 

이 규칙에서 나온 코드가 아래 코드에서 30번째 라인의 코드이다.

3~5까지는 모두 공백(n%3==1일때)으로 출력이 되도록 3으로 나눈 값의 몫만을 취해서 재귀로 호출한다.

그렇다면 9,9는 3,3이 되고, 다시 1,1이 되면서 빈 공백을 출력하게 된다.

나머지는 제외한 몫만을 취급하기 때문에

(17,17, 27) => (5,5,9) => (1, 1, 3)이 되면서 num이 1이 되기전에 line 20에서 분기에 걸려 " " 빈 공백을 출력하게 된다.

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const num = parseInt(input[0])
 
const lines = []
 
printStars(num);
console.log(lines.join(""))
 
function printStars(num) {
  for(let i = 0; i < num; i++) {
    for(let j = 0; j < num; j++) {
      star(i, j, num)
    }
    lines.push("\n")
  }
}
 
function star(i, j, num) {
  if(i % 3 == 1 && j % 3 == 1) {
    // (1,1), (1,4), (1,7)...
    lines.push(" ")
  } else {
    if(num == 1) {
      lines.push("*")
    } else {
      // (3,3) = (1,1)이 되고,
      // (3,4) = (1,1)이 된다.
      // (9,9), (27,27)도 동일한 방식으로 재귀 호출된다.
      star(parseInt(i/3), parseInt(j/3), parseInt(num/3))
    }
  }
}