Baekjoon2447: 별 찍기 - 10

문제

재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.

추상화

1) 모양 자체에서 규칙성을 발견한다
→ 한 줄 한 줄로는 규칙성을 찾을 수 없다

 

1항: *을 첫째줄 3번 출력 - 둘째줄 중앙 1만큼을 비운다 - 셋째줄 3번 출력

2항: 이전 패턴을 첫째줄 3번 출력 - 둘째줄 중앙 3만큼 비운다 - 셋째줄 3번 출력

3항

2) java 반복문을 위한 규칙성 정리
3항과 4항을 비교해보자

3항의 첫째줄을 3번 반복 = 4항의 첫째줄
3항의 둘째줄을 3번 반복 = 4항의 둘째줄
                            ...
3항의 아홉째줄을 3번 반복 = 4항의 아홉째줄


3항의 첫째줄을 1번 반복 + 3항의 길이만큼 띄어쓰기 + 첫째줄을 1회반복
3항의 둘째줄을 1번 반복 + 3항의 길이만큼 띄어쓰기 + 첫째줄을 1회반복
                           ...
3항의 아홉째줄을 1번 반복 + 3항의 길이만큼 띄어쓰기 + 아홉째줄을 1회반복

3) 코드화
i) 0항에 *을 넣고 반복문을 통해 문양을 저장한다
ii) 줄바꿈 "₩n"을 같이 저장할 수 있지만 같이 저장하면 다음 항에 값을 입력할 때 다시 줄바꿈의 위치를 바꿔야 하는 문제가 발생한다
         → 줄바꿈의 단계를 따로 만들어준다
         →즉, 배열 안 String 데이터들에는 줄바꿈이 없는 한 줄의 텍스트가 있는 것이다
iii) 텍스트 저장: 1항 = 3X3
         → 2항 첫째줄: 1항의 index[0] index[3의 1승 - 1]을 3번 반복
         → 2항 둘째줄: 1항의 index[3의 1승] index[3의 1승X2 - 1]을 3번 반복
         → 2항 셋째줄: 1항의 index[3의 1승X2] index[3의 1승X3 - 1]을 3번 반복
n항을 3구역으로 나누어서 정의해본다
1구역) n-1항의 index[0]~index[3의 n-1승 -1]을 3번 반복 + .... + n-1항의 index[3의 n-1승 X 2]~index[3의 n승-1]을 3번 반복
2구역) n-1항의 index[0]~index[3의 n-1승 -1]을 1번 반복+띄어쓰기+ n-항의 index[3의 n-1승 X 2]~index[3의 n승-1]을 1번 반복
3구역) = 1구역과 동일

4) 텍스트의 연산이 많으므로 StringBuilder을 활용한다

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 StringBuilder st = new StringBuilder();
	 StringBuilder blank = new StringBuilder();
	 String[] star = new String[8]; //0~7항까지 배열에 저장
	 star[0] = "*"; //시작을 위해 넣어준다
     
	 for(int i =1; i < 8; i++) {
		 int length = (int)Math.pow(3, i-1); //i항을 작성하기 위해 i-1항의 길이를 가져온다
		 for(int j = 0; j<length; j++) {
			 blank.append(" "); //공백도 미리 만들어준다
		 }
		 for(int j = 0; j<length; j++) { //첫째 구역
			 int start = j*length;
			 int last = (j+1)*length;
//이전 항의 문자값은 substring을 통해 가져온다: 0, 3을 적으면 index[0]~index[2]까지 가져온다
			 st.append(star[i-1].substring(start, last));
			 st.append(star[i-1].substring(start, last));
			 st.append(star[i-1].substring(start, last));
		 }
		 for(int j = 0; j<length; j++) { //둘째 구역
			 int start = j*length;
			 int last = (j+1)*length;
			 st.append(star[i-1].substring(start, last));
			 st.append(blank.toString());
			 st.append(star[i-1].substring(start, last));
		 }
		 for(int j = 0; j<length; j++) { //셋째 구역
			 int start = j*length;
			 int last = (j+1)*length;
			 st.append(star[i-1].substring(start, last));
			 st.append(star[i-1].substring(start, last));
			 st.append(star[i-1].substring(start, last));
		 }
		 star[i] = st.toString();
		 st.delete(0, st.length());
		 blank.delete(0, blank.length());
//매번 사용한 StringBuilder를 초기화한다: 공백 데이터 또한 초기화하는 것을 잊으면 안된다
	 }
	 for(int i =1; i < 8; i++) {
		 int length = (int)Math.pow(3, i);
		 int indexplus = 0;
		 st.append(star[i]);
		 for(int j = 1; j<length; j++) {
			 int now = j*length +indexplus;
			 st.insert(now, "\n");
			 indexplus++;
		 }
//작성해준 배열에서 줄바꿈을 추가한다.
//줄바꿈을 추가할 때마다 index의 개수가 증가하는 것을 고려한 변수 now를 생성한다
		 star[i] = st.toString();
		 st.delete(0, st.length());
//줄바꿈한 값을 넣어주고 초기화
	 }
     int N = Integer.parseInt(br.readLine());
     int number = 0;
     while(N!=1) {
    	 N /= 3;
    	 number++;
//입력값은 3의 제곱으로 주어지는데 반복문을 통해 입력값의 지수승을 구한다
     }
     System.out.print(star[number]);
}	 
}

 

 

개선: 이중배열의 사용

이중배열을 27X27크기로 만들었다고 가정한다: arr[27][27]

27X27은 9X9를 사용한 패턴이고 9X9는 3X3을 이용한 패턴이다

1) 주어진 입력값 N으로 빈 논리배열 [N][N]을 만든다
→ 공백 아니면 '*'을 사용하므로 boolean, 논리배열을 사용한다

2) 0항의 index[0][0]을 통해(*) 1항을 만들 수 있다 (*** * * ***)
     1항의 index[0][0]~index[2][2]를 통해 2항을 만들 수 있다

3) 이와 같은 규칙성을 활용해 배열을 채우고 배열의 내용과 줄바꿈을 이용해 출력한다
      N = 27 예시
      <1구역을 9구역에 모두 복사하기>
        → 배열에는 총 9개의 구역이 있다
        → 반복문을 통해 9개의 구역의 '시작점'에서 시작할 수 있다(for 2번사용)
        → '시작점'에서 index[0]~index[2]의 값을 복사한다(for 2번사용)
       ※ 결과: 9개의 구역에 1번 구역이 전부 복사되어있다
         
      <5구역 비우기>
      →N=27인 경우 index[3][3]부터 index[6][6]까지 false로 만들어준다

4) StringBuilder를 통해 true면 *, false면 " "추가하기

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 StringBuilder st = new StringBuilder();
	 int N = Integer.parseInt(br.readLine());
	 boolean[][] star = new boolean[N][N];
//입력받은 N을 통해 NXN 배열을 만든다
	 star[0][0] = true; // 0항 = "*"을 넣어준다
     
	 makeStar(N, star); //메소드를 만들어준다. 아래 메소드 정의 부분으로 간다
     
     //메소드를 통해 false, true표시한 내용을 출력하는 구간
	 for(int i=0; i<N; i++) {
		 for(int j=0; j<N; j++) {
			 if(star[i][j]==true) {
				 st.append("*");
			 } else {st.append(" ");}
		 }
		 st.append("\n");
	 }
	 System.out.println(st.toString());
}
public static void makeStar(int N, boolean[][] star) {
  int x = 3;
//초기값 x를 지정해준다
  while( N*3 != x) {
//while문의 loop 한 바퀴마다 x에 3이 곱해진다. x가 N보다 커지면 반복문이 멈춘다
	  int length = x/3;
//N = 27이라면 3X3의 배열을 9번 복사하기 때문에 27을 3으로 나눠서 기준 길이를 만든다

	for(int i = 0; i<length*3; i+=length) {
		  for(int j=0; j<length*3; j+=length) {
//위 두 개의 for문으로 각 구역의 시작 좌표를 설정할 수 있다. star[i][j]

			for(int k=0; k<length; k++) {
				  for(int m =0; m<length; m++) {
					  star[i+k][j+m] = star[k][m];
//각 구역의 시작점에서 1구역의 내용을 복사해줄 for문들이다
				  }
			  }
		  }
	  }
//9개의 구역에 모두 복사한 후 5구역을 비워준다
	  for(int k=length; k<length*2; k++) {
		 for(int m =length; m<length*2; m++) {
			star[k][m] = false;
				 }
			 }
	  x *= 3;
  }
 
}
}

*코드 길이와 계산시간이 단축되었다