크래프톤 정글 WEEK5 Day 35

📆2024.2.11

 

오늘 과제 연결리스트 다 풀었다!! 사실 스스로 혼자 풀었다고는 할 수 없고 챗 GPT의 도움과 동료분들의 도움으로 풀었는데 그래도 하나하나 이해하고 넘긴 부분은 뿌듯하다.

내일은 스택 큐 풀고 CSAPP 책 좀 읽어봐야겠다.

 

---

 

과제 - 연결리스트

alternateMergeLL

1. 두 번째 리스트의 노드를 첫 번째 리스트의 번갈아가는 위치에 삽입한다.
2. 두 번째 리스트의 노드는 첫 번째 리스트에 번갈아가는 위치가 있는 경우에만 삽입되어야 한다.

 

내가 짠 코드

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    ListNode *L1 = ll1->head;
    ListNode *L2 = ll2->head;
    
    while(L1 != NULL && L2 != NULL)
    {
    	ll2->head = L2->next;  //ll2의 head를 L2의 다음 노드로 업데이트
        L2->next = L1->next;   //L2의 다음 노드를 L1의 다음 노드로 설정
        L1->next = L2;         //L1의 다음 노드를 L2로 설정
        
        L1 = L1->next->next;   //L1의 노드를 L1의 다음 다음 노드로 설정
        L2 = ll2->head;	       //L2의 노드를 ll2의 헤드로 설정
        
        ++(ll1->size);
        --(ll2->size);
    }
}

 

chat gpt의 도움을 받아 풀었는데 사실 좀 이해가 안가서 풀이를 봤더니 풀이의 구현이 더 이해가 가고 간단한 거 같다.

 

 

풀이

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    ListNode *temp;
    int fixsize1 = ll1->size;
    int fixsize2 = ll2->size;
    int inspos = 1; 
    
    if(fixsize1 >= fixsize2)
    {
    	while(ll2->size > 0)
        {
            temp = findNode(ll2, 0);
            insertNode(ll1, inspos, temp->item);
            removeNode(ll2,0);
            inspos +=2;
         }
     }
     else{
     	while(fixsize1 > 0)
        {
            temp = findNode(ll2,0);
            insertNode(ll1, inspos, temp->item);
            removeNode(ll2,0);
            inspos +=2;
            fixsize1 -= 1;
         }
     }
 }

 

ll1의 size가 ll2의 size보다 크거나 같으면 findNode()를 사용해서 ll2의 값을 temp에 넣고 ll1의 1,3,5... 등 사이사이에 insert 하고 ll2의 노드를 삭제해 주고,

 

ll1의 size가 ll2의 size보다 작으면 동일하게 사이사이에 넣어주면서 fixsize를 1씩 줄여주면서 fixsize의 길이만큼만 삽입해 주도록 한다.

이 구현 방식이 더 이해가 가고 깔끔한 거 같다는 생각이 든다.

 

 

moveOddItemsToBackLL

1. 홀수를 모두 뒤로 옮긴다.

이 부분을 풀면서 많은 시간을 할애해서, 결국 다른 동료분의 코드를 참고해 봤는데 odd를 찾고 연결리스트의 마지막 노드에 추가해 주는 부분을 따로 구분하지 않고 while문 안에서 같이 돌려서(?) 안 됐던 거 같다.

그리고 이해하는 부분에서도 시간이 좀 걸렸지만, 코드 하나하나 디버깅해서 확인해 보니 유레카.. 를 외치게 되었다..

 

void moveOddItemsToBack(LinkedList *ll)
{
	/* add your code here */
	if (ll == NULL || ll->head == NULL )	
		return;
	
	ListNode *cur = ll->head;
	ListNode *prev, *odd, *tail = NULL;
	
	while (cur != NULL)
	{
		//현재 노드가 홀수이면
		if(cur->item % 2 != 0)
		{	
			if(odd == NULL)		//odd 리스트에 추가
			{
				odd = cur;		//현재 노드를 odd 첫 번째 노드로 설정
				tail = cur;		//현재 노드를 tail로 설정
			}
			else
			{
				tail->next = cur;	//tail의 다음 노드를 현재 노드로 설정
				tail = cur;			//tail을 현재 노드(마지막 노드)로 설정
			}
			//이전값 없으면
			if(prev == NULL)
			{
				ll->head = cur->next;
			}
			else
			{
				prev->next = cur->next;	//현재 노드의 다음 노드를 이전 노드의 다음 노드로 설정
			}
		}
		//짝수이면
		else
		{
			prev = cur;		//이전 노드를 현재 노드로 업데이트
		}
		cur = cur->next;	//현재 노드를 다음 노드로 업데이트
	}

	//odd리스트가 비어있지 않으면
	if(odd != NULL)
	{
		tail->next = NULL;		
		
		if(prev == NULL)
		{
			ll->head = odd;		
		}
		else
		{
			prev->next = odd;	
		}
	}
}

 

 

moveEvenItemsToBackLL

1. 짝수를 모두 뒤로 옮긴다.

이 문제는 홀수 문제랑 똑같아서 변수랑 짝수 찾는 부분만 변경해 주면 된다.

void moveEvenItemsToBack(LinkedList *ll)
{
	/* add your code here */
	if(ll == NULL && ll->head == NULL)
		return;

	ListNode *cur = ll->head;
	ListNode *even , *prev , *tail = NULL;

	while(cur != NULL)
	{
		if(cur->item %2 == 0)
		{
			if(even ==NULL)
			{
				even = cur;
				tail = cur;
			}
			else
			{
				tail->next = cur;
				tail = cur;
			}
			if(prev ==NULL)
			{
				ll->head = prev;
			}
			else
			{
				prev->next = cur->next;
			}
		}
		//홀수이면
		else
		{
			prev = cur;
		}
		cur = cur->next;
	}
	if(even !=NULL)
	{
		tail->next =NULL;
		if(prev ==NULL)
		{
			ll->head = even;
		}
		else
		{
			prev->next = even;
		}
	}
}

 

 

frontBackSplitLL

 

1. 단일 연결리스트를 두 개의 서브리스트로 분할한다.
2. 하나는 전반부(frontList), 다른 하나는 후반부(backList)를 나타낸다.
3. 원소의 개수가 홀수인 경우, 추가 원소는 전반부 리스트에 포함한다.

이 문제는 동료분께서 플로이드의 토끼와 거북이 알고리즘을 응용해서 풀면 된다라고 하면서 알려주셨다.

토끼와 거북이 알고리즘은 처음 들어봤다. 이런 알고리즘이 있는지도 몰랐다.

시간이 된다면 토끼와 거북이 알고리즘도 공부해 봐야겠다.

 

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
    ListNode *temp1 = ll->head;  
    ListNode *temp2 = ll->head->next;
   
    while(temp2 != NULL)           //리스트의 끝에 도달할 때까지
    {
    	temp2 = temp2->next;       //temp2를 한 칸 앞으로 이동(총 두 칸 이동시키기 위해서)
        if(temp2 != NULL)          //이동한 temp2가 null이 아니라면
        {
            temp1 = temp1->next;	//temp1 한 칸씩 더 이동
            temp2 = temp2->next;	//temp2 한 칸씩 더 이동 (총 두 칸 이동)
        }
    }
    resultFrontList->head = ll->head;  
    resultFrontList->size = ll->size / 2; 
    resultBackList->head = temp1->next;   //temp1은 중간에 위치
    resultBackList->size = ll->size - resultFrontList->size;
    
    temp1->next = NULL;     //두 리스트를 완전히 분리
}

 

temp1은 한 노드씩 이동하고, temp2는 두 노드씩 이동한다. 

temp2가 NULL이 된다는 말은 연결리스트의 끝까지 다 이동했다는 의미로 temp2가 리스트의 끝에 도달하면 temp1은 중간에 위치하게 된다.

 

resultFrontList->head를 ll->head로 설정해 주고, size는 리스트의 사이즈를 2로 나눈 수로 설정한다.

 

resultBackList->head를 temp1->next로 설정해 주는 이유는

temp1 리스트는 중간에 위치하기 때문에 temp1의 다음 노드를 head로 설정하는 것이다.

resultBackList->size는 리스트의 전체 사이즈에서 resultFrontList의 사이즈를 뺀 값이 된다.

 

그리고 temp1->next를 NULL로 해주는 이유는 두 리스트로 완전히 분리해야 하기 때문에, temp1의 다음 노드를 null로 해줌으로써 완전히 분리된다.

-> 실제 이 코드를 안 썼다가 에러가 뜨고, 두 리스트로 완전히 분리가 안었다. 

-> resultFrontList : 1 2 3 4 5 6

-> resultBackList : 5 6

 

 

moveMaxToFront

1. 최대한 한 번만 연결리스트를 순회하는 함수를 작성한다.
2. 그리고 가장 큰 값을 저장한 노드를 리스트의 앞쪽으로 이동한다.

이 문제는 비교적 금방 풀었다.

int moveMaxToFront(ListNode **ptrHead)
{
    ListNode *temp = *ptrHead;    //리스트의 head를 가리킴
    ListNode *prev = NULL;	    
    ListNode *max = *ptrHead;    
    
    if(temp ==NULL)	   //head가 null이면
    	return 0;
    
    while(temp->next != NULL)    //리스트의 끝에 도달할 때까지
    {
    	if(temp->next->item > max->item)
        {
            prev = temp;        //이전 노드를 현재 노드로 설정
            max = temp->next;   //max를 다음 노드로 업데이트
        }
        temp = temp->next;      //다음 노드로 이동
     }
     if(max != *ptrHead)        //만약 max가 헤드가 아니라면
     {
        prev->next = max->next;  //prev의 다음 노드를 max의 다음 노드로 
        max->next = *ptrHead;    //max의 next를 헤드로
        *ptrHead = max;          //헤드를 max로 업데이트
     }
     return 0;
}

 

전체적으로 리스트를 한 번만 순회하므로 시간 복잡도 O(n)

 

recursiveReverse

1. 주어진 연결리스트의 next 포인터와 head 포인터를 변경하여 재귀적으로 연결리스트를 뒤집는 함수를 작성한다.

-> 함수 내부에서 자기 자신을 호출하여 리스트의 노드를 하나씩 처리하면서 리스트를 뒤집어야 한다.

 

마지막에 현우님이 설명해 주셔서 설명 듣고 pdf 파일에 있는 힌트 주워 담아서 구현하니까 됐다.

void RecursiveReverse(ListNode **ptrHead)
{
     if(*ptrHead == NULL || (*ptrHead)->next == NULL)  //리스트가 비어있거나, 리스트에 노드가 하나라면
     	return;
     
     ListNode *first = *ptrHead;
     ListNode *rest = first->next;
     
     RecursiveReverse(&rest);
     
     //현재 노드를 다음 노드의 다음으로 설정하여 역순으로 연결
     first->next->next = first;
     first->next = NULL;    //뒤집힌 리스트의 끝을 표시한다.
     
     *ptrHead = rest;       //새로운 헤드를 설정한다.
}

 

리스트 한 번 순회하므로 시간 복잡도 O(n)