📦 자료 구조 구현 과제

---

📌 Q2_A_LL

Write a C function alternateMergeLL() which inserts nodes of the second list into alternate positions of the first list. The nodes of the second list should only be inserted when there are alternate positions available in the first list.

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
	ListNode* ll1_Node = ll1->head;
	ListNode* ll2_Node = ll2->head;
	int ll1_originSize = ll1->size;
	int ll2_originSize = ll2->size;

	for (int i = 0; i < ll2_originSize; i++)
	{
		// ll2의 인덱스가 ll1 인덱스 길이를 초과하면
		if(i >= ll1_originSize){
			ll2->head = ll2_Node;
			return;
		}
		
		// ll1의 각 노드 오른쪽에 ll2 요소 하나씩 넣기
		ListNode *ll1_nextNode = ll1_Node->next;
		ListNode *ll2_nextNode = ll2_Node->next;
		ll2_Node->next = ll1_Node->next;
		ll1_Node->next = ll2_Node;
		ll1->size++;
		ll2->size--;
		// 다음 노드로 바꿔주기
		ll1_Node = ll1_nextNode;
		ll2_Node = ll2_nextNode;
	}
	ll2->head = NULL;
	return;
}

두번째 연결 리스트를 순회하면서

두번째 연결 리스트의 노드에
첫번째 연결 리스트의 노드의 다음 노드를 연결시켰고

첫번째 연결 리스트의 노드에는
두번째 연결 리스트의 노드를 연결시켰다.

연결을 여러 번 실수해서 무한 순회가 자꾸 발생했다.
그림을 그려 확인하니 문제를 바로 발견해서 고칠 수 있었다.

📌 Q3_A_LL

(moveOddItemsToBackLL) Write a C function moveOddItemsToBackLL() that moves all the odd integers to the back of the linked list.

void moveOddItemsToBack(LinkedList *ll)
{
	// 꼬리 찾기
	ListNode *tail = ll->head;
	while(tail->next != NULL){
		tail = tail->next;
	}

	// 순회하면서 홀수면 꼬리로 보내버리기
	ListNode *node = ll->head;
	ListNode *pre_node = node;
	ListNode *next_node = node->next;
	for (int i = 0; i < ll->size; i++){
		
		if(node->item % 2 != 0) {
			pre_node->next = node->next;
			next_node = node->next;
			tail->next = node;
			tail = node;
			node->next = NULL;

			// 보내려던 값이 헤드였다면 변수들 초기화
			if(ll->head == node) {
				ll->head = next_node;
				node = next_node;
				pre_node = next_node;
				next_node = next_node->next;
				continue;
			}
		} else {
			pre_node = node;
		}

		node = next_node;
		if (node != NULL){
			next_node = node->next;
		}
	}
	return;
}

버그 1. 보내려던 값이 헤드면 프린트를 제대로 못함

보내려던 값이 헤드면 pre_node, node, next_node 등
변수들을 전부 초기화시켜서 해결.

버그 2. 홀수를 연속 2번 보내버리면 이전 노드 저장을 제대로 못함

node가 홀수일 때 이전 노드를 저장하는 pre_node를 갱신해버리면
뒤로 보낸 홀수인 node로 pre_node가 갱신되어버림.

else 문 안에 pre_node를 넣어 해결.

버그 3. 뒤로 보낸게 아무것도 없으면 마지막 노드의 다음 노드가 NULL

다음 노드를 저장하는 next_node에 값을 갱신할 때
뒤로 보낸게 아무도 없으면 next_node = node->next에서 node가 NULL이라
segmentation 오류가 난다.

if (node != NULL) 문 넣어서 해결.

📌 Q5_A_LL

(frontBackSplitLL) Write a C function frontBackSplitLL() that splits the singly linked list into two sublists – one for the front half, and one for the back half. If the number of elements is odd, the extra element should go into the front list. The frontBackSplitLL() prints two lists which contains frontList and backList.

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	ListNode *ptr = ll->head;
	
	if (ptr == NULL) {
		return;
	}

	// 짝수면 그냥 2로 나누면 됨. 홀수면 2로 나누고 +1
	int divLen = (ll->size % 2 == 0) ? ll->size / 2 : ll->size / 2 + 1;

	// head에 넣어주고 연결 끊기
	resultFrontList->head = ptr;
	resultFrontList->size = divLen;
	for (int i = 0; i < divLen-1; i++) {
		ptr = ptr->next;
	}
	ListNode *backStart = ptr->next;
	ptr->next = NULL;

	resultBackList->head = backStart;
	resultBackList->size = ll->size - divLen;

	return;
}

ll의 첫번째 요소를 frontlist의 head에 연결시켰고,
ll의 절반 인덱스는 backlist의 head에 연결시켰다.
이렇게 하면 구현은 편한데 frontlist와 backlist가 ll에 종속되어버린다.

ll과 별도로 생성하려면 일일이 malloc 해줘야될텐데 귀찮.

📌 Q6_A_LL

(moveMaxToFront) Write a C function moveMaxToFront() that traverses a linked list of integers at most once, then moves the node with the largest stored value to the front of the list.

int moveMaxToFront(ListNode **ptrHead)
{
	ListNode *maxNode = *ptrHead;
	ListNode *pre_maxNode = *ptrHead;
	ListNode *next_maxNode = (*ptrHead)->next;
	int max = (*ptrHead)->item;
	ListNode *ptr = *ptrHead;
	ListNode *pre_ptr = *ptrHead;
	// 전부 순회하고 최댓값 노드 찾기
	while(ptr != NULL){
		if(max < ptr->item){
			// 최댓값 관련 변수들 갱신
			max = ptr->item;
			pre_maxNode = pre_ptr;
			maxNode = ptr;
			next_maxNode = maxNode->next;
		}
		pre_ptr = ptr;
		ptr = ptr->next;
	}
	// 최댓값 노드를 앞으로 보내고 헤드 갱신
	pre_maxNode->next = next_maxNode;
	maxNode->next = *ptrHead;
	*ptrHead = maxNode;
}

버그 1. 최댓값 노드의 이전 노드 저장 실수

pre_maxNode를 maxNode로 갱신하고 있었다.
현재 최댓값으로 판명된 노드의 이전 노드가 아니라,
이전 최댓값 노드를 현재 최댓값 노드의 이전 노드로 갱신하고 있었다는 뜻.

pre_ptr을 새로 만들어서 할당했더니 해결되었다.

📌 Q7_A_LL

(recursiveReverse) Write a C function recursiveReverse()that recursively reverses the given linked list by changing its next pointer and its head pointer.

void RecursiveReverse(ListNode **ptrHead)
{
	ListNode *ptr = *ptrHead;
	ListNode *pre_ptr = NULL;
	ListNode *next_ptr = (*ptrHead)->next;
	while(ptr != NULL){
		// 다음에 갈 노드 저장해놓고
		next_ptr = ptr->next;
		// 노드 이전 노드에 연결하고
		ptr->next = pre_ptr;
		// 다음 노드를 찾기 위해 변수 갱신하기
		pre_ptr = ptr;
		ptr = next_ptr;
	}
	*ptrHead = pre_ptr;
	return;
}

재귀적으로 풀라는게 맨 뒤에서부터 하라는 건가 싶었긴 한데
굳이 맨 뒤로 갔다가 다시 앞으로 돌아오는 연산을 할 필요가 있나? 싶어서
그냥 앞에서부터 계속 이전 노드에 연결시켜줬다.

📌 Q1_C_SQ

(createQueueFromLinkedList) Write a C function createQueueFromLinkedList() to create a queue (linked-list-based) by enqueuing all integers which are stored in the linked list. The first node of the linked list is enqueued first, and then the second node, and so on. Remember to empty the queue at the beginning, if the queue is not empty.

void createQueueFromLinkedList(LinkedList *ll, Queue *q)
{
	q->ll.head = ll->head;
	q->ll.size = ll->size;
}

어쩌라는 건지 모르겠어서 그냥 그대로 복사함.
문제 만든 의도는 원본 ll 일일이 순회하면서 malloc해서 노드를 새로 만들어주라는 것 같은데
귀찮아서 패스.
removeOddValues 뭐시기도 문제에 일단 안 쓰여있었으니까 패스.

📌 Q3_C_SQ

(isStackPairwiseConsecutive) Write a C function isStackPairwiseConsecutive() that checks whether numbers in the stack are pairwise consecutive or not. Note that the isStackPairwiseConsecutive() function only uses push() and pop() when adding or removing integers from the stack.

int isStackPairwiseConsecutive(Stack *s)
{
	bool isPC = true;
	while(!isEmptyStack(s)){
		int int_1 = pop(s);
		int int_2 = pop(s);
		if(!(int_1 + 1 == int_2 || int_1 - 1 == int_2)){
			isPC = false;
			break;
		}
	}
	return isPC;
}

스택 큐 문제부턴 혼자서 구현할 필요가 없어보여서 이미 구현돼있던 함수들을 써봤는데 금방 풀렸다.
isEmptyStack 제공해주는 거랑 비어있을 때 pop()하면 INT_MIN 반환해주는 것도 편했다.

📌 Q4_C_SQ

(reverseQueue) Write a C function reverseQueue() to reverse a queue using a stack. Note that the reverseQueue() function only uses push() and pop() when adding or removing integers from the stack and only uses enqueue() and dequeue() when adding or removing integers from the queue. Remember to empty the stack at the beginning, if the
stack is not empty.

void reverse(Queue *q)
{
	// 큐에서 데이터 빼서 스택에 담은 다음 큐에 다시 담아라~
	Stack *rS;
	rS = (Stack *)malloc(sizeof(Stack));

	while(!(isEmptyQueue(q))){
		push(rS, dequeue(q));
	}
	while(!(isEmptyStack(rS))){
		enqueue(q, pop(rS));
	}

	free(rS);
}

1 2 1 2 3 넣었을 때 안돼서 한참을 코드를 들여다보다
아무리 봐도 문제가 없는 것 같아서
그냥 다시 한 번 돌려봤는데 아무 문제 없이 동작했다.

뭐지? 하고 그냥 넘어가려다가 마지막으로 또 한 번만 다시 해봤더니
첫번째 1 2 1 2 3은 되는데
두번째 1 2 1 2 3은 안됐다.

(디버그로 원인 파악함)

void reverse(Queue *q)
{
	// 큐에서 데이터 빼서 스택에 담은 다음 큐에 다시 담아라~
	Stack *rS;
	rS = (Stack *)malloc(sizeof(Stack));
	rS->ll.size = 0;

	while(!(isEmptyQueue(q))){
		push(rS, dequeue(q));
	}
	while(!(isEmptyStack(rS))){
		enqueue(q, pop(rS));
	}

	free(rS);
}

malloc이 메모리를 초기화 안 시켜줘서 그랬던거였다.
rS->ll.size = 0; 추가하니까 여러 번 해도 정상 작동함.

void reverse(Queue *q)
{
	// 큐에서 데이터 빼서 스택에 담은 다음 큐에 다시 담아라~
	Stack *rS;
	rS = (Stack *)calloc(1,sizeof(Stack));
	// rS->ll.size = 0; <- malloc으로 바꾸면 이거 추가

	while(!(isEmptyQueue(q))){
		push(rS, dequeue(q));
	}
	while(!(isEmptyStack(rS))){
		enqueue(q, pop(rS));
	}

	free(rS);
}

calloc 써도 되는듯.

📌 Q5_C_SQ

(recursiveReverseQueue) Write a recursive C function recursiveReverseQueue() int temp; that reverses the order of items stored in a queue of integers.

왜 또 거꾸로 하라고 시키는거지? 하고 봤더니 재귀를 써서 거꾸로 만들라고 함.
아까 7번 문제도 재귀 쓰라는 거였는듯. 근데 여기서 재귀 써보면 되니까 다시 돌아가서 풀진 않을거임.

void recursiveReverse(Queue *q)
{
	int saved = dequeue(q);
	if (!(isEmptyQueue(q))){
		recursiveReverse(q);
	}
	enqueue(q, saved);
}

구현하고 보니까 재귀가 훨씬 쉬웠다.
함수도 건드리지 말고 무조건 void recursiveReverse(Queue *q) 이대로 재귀하라길래
한참 헤맸는데, 억지로 매개변수 늘려서 했으면 이렇게 간단하게 못 만들었을 것 같다.

dequeue의 리턴값이 정수값이라는 사실을 모르고(까먹고?)
saved를 ListNode *saved 로 선언했다가 왜 saved에 deque한게 안 들어가지? 이러고 있었다. int로 바꿨더니 정상 동작.

📌 Q6_C_SQ

(removeUntilStack) Write a C function removeUntilStack() that pops all values off a stack of integers until the first occurrence of the chosen value.

void removeUntil(Stack *s, int value)
{
	// 스택 빌때까지 pop 시도하다가 
	// 찾던 value 나오면 다시 스택에 넣고 종료
	int seek = pop(s);

	while(!(isEmptyStack(s))) {
		if (seek == value) {
			push(s,seek);
			break;
		}
		seek = pop(s);
	}
}

슬슬 너무 쉬워서 어처구니가 없다.

📌 Q7_C_SQ

(balanced) Write a C function balanced() that determines if an expression comprised of the characters ()[]{} is balanced. The prototype for the balanced() function is given below:

int balanced(char *expression)
{
	// 문자열 순회하면서 왼쪽 괄호 만나면 스택에 넣고
	// 오른쪽 괄호 만나면 스택에서 뺀다
	// 문자열 순회 완료했는데 스택 비어있으면 balanced

	Stack *s;
	s = (Stack *)calloc(1,sizeof(Stack));

	for (char *ptr = expression; *ptr != '\0'; ptr++) {
		if (*ptr == '{' || *ptr == '[' || *ptr == '(') {
			push(s, *ptr);
		} 
		else if(*ptr == ')') {
			if (pop(s) != '(') {
				return true;
			}
		} else if(*ptr == ']') {
			if (pop(s) != '[') {
				return true;
			}
		} else if(*ptr == '}') {
			if (pop(s) != '{') {
				return true;
			}
		}
	}
	free(s);
	return false;
}

살짝 노가다로 풀어서 아쉽다.

for (const char *ptr = expression; *ptr != '\0'; ptr++) {
    if (*ptr == '{' || *ptr == '[' || *ptr == '(') {
        push(s, *ptr);
    } else if (*ptr == ')' || *ptr == ']' || *ptr == '}') {
        if (isEmptyStack(s)) {
            free(s);
            return false; // 닫는 괄호가 남는 경우
        }
        char open = pop(s);
        if ((*ptr == ')' && open != '(') || (*ptr == ']' && open != '[') || (*ptr == '}' && open != '{')) {
            free(s);
            return false;
        }
    }
}

gpt한테 어떻게 우아하게 풀 방법 없냐고 물어봐서 받은 코드. 결국 노가다인듯.
그러고보니 free를 안했다. calloc이라 오류 내뿜는 실수는 아니지만, 실무에선 치명적인 오류가 될 수도 있을테니 경계해두자.