백준 2447번 별찍기 - 10

https://www.acmicpc.net/problem/2447

내 코드

#include <stdio.h>

char array[6561][6561];

void space(int y, int x, int n)//(x,y)를 시작점으로 길이 n인 정사각형을 범위로 공백을 찍어낸다.
{
	int i, j;
	for (i = y; i < y + n; i++)
	{
		for (j = x; j < x + n; j++)//여기서 오타가 났는데 오타를 발견하지 못해 고생했었다 ㅎㅎ
		{
			array[i][j] = ' ';
		}
	}
}

void star(int y, int x, int n)//(x,y)를 시작점으로 길이 n인 정사각형에 별을 찍는 함수
{
	if (n == 3)
	{
		array[y][x] = '*';
		array[y][x + 1] = '*';
		array[y][x + 2] = '*';
		array[y + 1][x] = '*';
		array[y + 1][x + 1] = ' ';
		array[y + 1][x + 2] = '*';
		array[y + 2][x] = '*';
		array[y + 2][x + 1] = '*';
		array[y + 2][x + 2] = '*';
		
	}
	else if (n > 3)
	{
		star(y, x, n / 3);
		star(y, x + n/3, n / 3);
		star(y, x + 2 * n/3, n / 3);
		star(y + n/3, x, n / 3);
		space(y + n/3, x + n/3, n / 3);//중간에 공백을 찍어야 하므로 스페이스 함수 따로 정의
		star(y + n/3, x + 2 * n/3, n / 3);
		star(y + 2 * n/3, x, n / 3);
		star(y + 2 * n/3, x + n/3, n / 3);
		star(y + 2 * n/3, x + 2 * n/3, n / 3);		
	}
}

int main()
{
	int i, N;
	scanf("%d", &N);
	star(0, 0, N);//처음 시작점은 당연히 0,0 정사각형의 길이는 주어진대로 N
	for (i = 0; i < N; i++)
	{
		printf("%s\n", array[i]);
	}
	return 0;
}

다른 사람 코드

내 코드의 시간이 60ms인데 비해 상위권 코드들은 시간이 40ms대여서 다른 코드들을 읽어보기로 했다.

an0520a님의 코드이다.

시간은 12ms, 메모리는 5792kb 소요.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

void sqaure_star(char* arr, unsigned int length, unsigned int nl);//왜 굳이 unsigned int 변수를 두개 주는걸까? 읽어봐야 알 것 같다.

int main()
{
	unsigned int n;
	scanf(" %u", &n);//N을 unsigned int로 받네? 이것도 왜일까?
	char* arr = (char*)calloc((n + 1) * n, sizeof(char));
    //calloc으로 arr를 받는구나.
    calloc을 잠시 복습해보자.
    malloc이랑 비슷하나 두가지 차이가 있다.
    1. calloc은 clean allocate로 메모리를 할당하고 모두 0으로 초기화해주는 역할까지 수행한다.
    2. malloc(n * k)를 하고 이 배열을 0으로 초기화라는 것은 calloc (n * k)와 같다.
    즉, malloc(5*sizeof(int)) 후 해당배열을 0으로 초기화하는 것은 calloc은 calloc(5,sizeof(int))로 쓴다.
    
    즉, 이는 arr를 (n + 1) * n칸 주는 것인데 이차원배열을 쓰지 않는 것이 특이점이다.

	memset(arr, '*', n * n); // 할당받은 (n + 1) * n칸의 메모리 중 n * n칸을 *로 채웠다. -> 일단 채워 놓았다는게 중요
	
	sqaure_star(arr, n, n + 1); //square star 함수가 어떤 함수인지 보고 와야겠다.

	for(unsigned int i = n; i < (n + 1) * n; i += n + 1) arr[i] = '\n'; // 그리고 n + 1칸씩 이동한 이유가 여기 나오는데 여기는 개행문자를 넣는다.
	memset(arr + n * n, '*', n - 1); 그리고 마지막에 *을 n - 1칸 채워넣는데 음 처음부터 n + 1 * n + 1칸 만큼 *을 채워넣으면 되는거 아닌가? 그리고 n - 1칸 채워넣으면 한 칸 부족할 거 같은데...
    
    아하 엔터를 n - 1개 치니까 ! *을 n - 1개 더 추가해주는거구나 !
    
    수식으로 보면 (n - 1) * (n + 1) + 1 - (n - 1 ) + (n - 1) = n^2

	printf("%s", arr);

	free(arr);
}

void sqaure_star(char* arr, unsigned int length, unsigned int nl)
{
	if(length == 1){ return; } // length 가 1이면 함수 종료

	else
	{
		unsigned int new_length = length / 3; // 3씩 길이가 나눠진다.
		sqaure_star(arr, new_length, nl); //nl이 무슨 의미인지 먼저 알아야 한다. nl은 안 바뀌는걸 보니 계속 처음 받았던 n에 1을 더한 값이다.
		sqaure_star(arr + new_length, new_length, nl);
		sqaure_star(arr + new_length * 2, new_length, nl);
		sqaure_star(arr + nl * new_length, new_length, nl);
       //(n + 1) * new_length 인 이유는 n칸 이후마다 개행문자를 집어넣을 것이기 때문이다.
		for(unsigned int i = 0; i < new_length; i++) memset(arr + nl * (new_length + i) + new_length, ' ', new_length);//공백을 중앙에 집어넣은 과정이다.
        전체가 81칸이라 하면 처음에 new length는 27이고 이차원 배열로 쳤을 때 newlength만큼 세로로 내려온 다음 가로로 newlength만큼 더 움직이고 그 다음 newlength만큼 공백을 채운뒤 다시 1칸씩 내려오는 것을 newlength만큼 반복하는 과정을 거친다.
        즉, 이는 *을 다 채워놓고 이를 내려가면서 행하는 탑 투 바텀이다.
		sqaure_star(arr + nl * new_length + new_length * 2, new_length, nl);
		sqaure_star(arr + nl * new_length * 2, new_length, nl);
		sqaure_star(arr + nl * new_length * 2 + new_length, new_length, nl);
		sqaure_star(arr + nl * new_length * 2 + new_length * 2, new_length, nl);
	}
}

결국 일차원 배열에 이를 넣고 배열 한칸 한칸에 문자를 넣는 것보다 빠른 memset를 이용해 빠르게 처리한 것이다.