동적할당 대신 배열을 사용해 시간 줄이기(feat. 코딩테스트)

코등테스트 문제를 풀 시에, 동적할당 대신 배열을 사용함으로써 시간을 save할 수 있는 방법.

int arr_idx = 0;

typedef struct Node {
	int value;
} Node;

#define MAX_SIZE	1000
Node a[MAX_SIZE];

Node *myAlloc(void)
{
	return &a[arr_idx++];
}

int main(void)
{
	...
}

위와 같이 필요한 순간에 마다 malloc() 함수를 통해 공간을 할당받는 것이 아니라,
필요한 만큼의 size를 미리 잡아두고(compile time에) 필요할 때마다 myAlloc() 함수를 통해 
미리 잡아둔 메모리 공간의 주소를 얻어오는 방식으로 시간을 save할 수 있다.

매 case가 시작될 때마다 'arr_idx = 0' 으로 초기화만 해주면 된다. 

Single Linked List를 사용하고자 할 때 sample code는 아래와 같다.

int arr_idx = 0;

typedef struct Node {
	int value;
	struct Node *prev;
} Node;

#define MAX_SIZE	1000
Node a[MAX_SIZE];

Node *myAlloc(void)
{
	return &a[arr_idx++];
}

int main(void)
{
	Node *pList = NULL;
	Node *p;

	arr_idx = 0;
	p = myAlloc();
	p->value = 1;
	p->prev = pList;
	pList = p;

	p = myAlloc();
	p->value = 2;
	p->prev = pList;
	pList = p;
	
	p = myAlloc();
	p->value = 3;
	p->prev = pList;
	pList = p;
	
	for (Node *pTemp = pList; pTemp != NULL; pTemp = pTemp->prev)
		printf("%d ", pTemp->value);
        
	// 3 2 1 출력 됨.
    
	return 0;
}

 

 

 

myAlloc()을 호출할때마다 일어나는 일을 그림으로 그려보면 다음과 같다.