BAEKJOON 10845 : 큐 for C

 

10845번: 큐

 이번에는 BAEKJOON 10845번이자 대표적인 선입선출의 구조를 같은 큐(Queue) 문제를 풀어봅니다.

 

---

Code.

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

typedef struct{
	int *arr;     // 데이터 메모리 포인터
	int maxLength;// 가용 가능한 공간 길이
	int length;   // 현재 데이터가 담긴 길이
}queue; // 큐의 정보를 담은 스트럭처

queue* newQueue(int maxLength){
	queue* temp = (queue *)malloc(sizeof(queue));
	temp->arr = (int *)malloc(sizeof(int) * maxLength);
	temp->maxLength = maxLength;
	temp->length = 0;
	return temp;
} // 새로운 큐를 생성하는 함수; 반환값 : 만들어진 큐의 주소

int delQueue(queue *q){
	if(q->arr && q->maxLength){
		free(q->arr);
		free(q);
		return 1;
	}
	return 0;
} // 생성되어있는 큐 삭제; 반환값: 삭제 성공 1, 삭제 실패(안함) 0

int push(queue* q, int value){
	if(q->maxLength <= q->length){
		q->maxLength *= 2;
		int *arr = (int *)malloc(sizeof(int) * q->maxLength);
		for(int i = 0 ; i < q->length;++i){
			arr[i] = q->arr[i];
		}
		free(q->arr);
		q->arr = arr;
	}
	q->arr[q->length++] = value;
	return 1;
} // 큐에 값 넣기; 반환값: 1

int pop(queue* q){
	if(q->length < 1){
		return -1;
	}else{
		int ret = q->arr[0];
		for(int i = 1; i < q->length;++i){
			q->arr[i-1] = q->arr[i];
		}
		q->length--;
		return ret;
	}
} // 큐에서 선입 값 뽑기; 반환값: 선입 값

int size(queue* q){
	return q->length;
} // 큐의 현재 길이 뽑기; 반환값: 큐의 현재 길이

int empty(queue* q){
	return q->length == 0;
} // 큐의 저장 상태 확인; 반환값: 큐에 임의의 값 저장됨 1, 큐가 비어있음 0

int front(queue* q){
	if(!q->length){
		// if length of q is zero
		return -1;
	}
	return q->arr[0];
} // 큐의 선입 값 확인; 반환값: 선입 값

int back(queue* q){
	if(!q->length){
		// if length of q is zero
		return -1;
	}
	return q->arr[q->length-1];
} // 큐의 최후입 값 확인; 반환값: 최후입 값

int main(void){
	queue* q = newQueue(10);
	
	int cmdCount;
	scanf("%d", &cmdCount);
	
	while(cmdCount--){
		char str[6];
		scanf("%s", str);
		int sum = 0;
		for(int i = 0 ; str[i]; ++i){
			sum += str[i];
		}
		
		switch(sum){
			case 448: // push
				{
					int num;
					scanf("%d", &num);
					push(q, num);
				}
				break;
			case 335: // pop
				printf("%d\n", pop(q));
				break;
			case 443: // size
				printf("%d\n", size(q));
				break;
			case 559: // empty
				printf("%d\n", empty(q));
				break;
			case 553: // front
				printf("%d\n", front(q));
				break;
			case 401: // back
				printf("%d\n", back(q));
				break;
		}
	}
	delQueue(q);
	return 0;
}

 이 코드에서 생소하게 느껴질 수 있는 부분이 아래에 주석으로 강조된 부분입니다.

		for(int i = 0 ; str[i]; ++i){
			sum += str[i];
		}

 어째서 입력받은 문자열의 값을 다 더하나 궁금하실 수 있는데 이는 약간의 문자열 처리 노하우라고 보면 될 것 같습니다. 일반적으로 문자열 처리 속도는 느리게 진행됩니다. 그도 그럴 것이 모든 값을 비교해서 같은지를 확인하는 과정을 문자열의 문자 개수만큼 진행하기 때문입니다. strcmp()의 코드를 확인하진 않았지만 어느 정도 제가 말한 것과 비슷하게 동작하리라 생각합니다.

 

 여기서 생각을 했습니다. 문자의 값을 다 더해서 해당 값을 비교하면 어떨가 하고 말이죠. 물론 이 방식의 단점은 아래 여러 문자열이 같은 문자열로 인식되는 단점이 있습니다.

문자의 위치만 바뀜	abcd	bcda	cdab	dabc
문자값의 합이 같음	abcd	bbbd	aadd	aace

위 <문자의 합이 같음>에 대한 확인용 코드는 다음과 같습니다.

#include <stdio.h>

int main(void){
	
	char* str[4] = {
		"abcd",
		"bbbd",
		"aadd",
		"aace"
	};
	
	for(int i = 0 ; i < 4;++i){
		int sum = 0;
		for(int k = 0 ; str[i][k];++k){
			sum+= str[i][k];
		}
		printf("%s : %d\n", str[i], sum);
	}
	
	return 0;
}

 

 그러나 문제의 제시된 여섯 가지 문자열 (push, pop, size, empty, front, back)은 서로 값이 다릅니다.

이 경우 또한 확인용 코드는 다음과 같습니다.

#include <stdio.h>

int main(void){
	
	char* str[] = {
		"push",
		"pop",
		"size",
		"empty",
		"front",
		"back"
	};
	
	for(int i = 0 ; i < 6;++i){
		int sum = 0;
		for(int k = 0 ; str[i][k];++k){
			sum+= str[i][k];
		}
		printf("%6s : %d\n", str[i], sum);
	}
	
	return 0;
}

 각 문자열의 값은 다음과 같습니다.

push	pop	size	empty	front	back
448	335	443	559	553	401

 따라서 이 값을 가지고 어떤 명령어가 들어왔는지 알 수 있습니다. 따라서 이를 기준으로 switch 문법을 통해 명령어 처리를 진행했습니다.

---

참고

 누차 위에서 문제점을 말씀드렸지만, 제가 작성한 코드는 속도 면에선 좋을지라도 몇 가지 단점을 가지고 있습니다. 따라서 이런 방식으로 문제를 해결하는 것은 확신이 들었을 때만 사용하기 바랍니다.

 

 제가 사용한 방법의 구조는 간단히 하면 해시맵(Hash map)을 이용한 것이라고 생각하면 될 것 같습니다. 물론 해시함수를 구성한 것은 아니지만, 문자열로 특정한 숫자 값을 만들었고 이 값들은 이 케이스에선 문자열과 일련의 작업으로 만들어진 숫자 값이 유일한 1대 1 매칭 구조를 가지고 있습니다.

---

더 배우기

 이번 코드를 통해 함수 포인터에 대해 알아보는 포스트를 추가했으니 관심 있다면 읽어보세요!

함수 포인터를 배워야하는 이유