[C] 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

가장 큰 값 찾아서 앞으로 옮기기

https://github.com/yeooonee/Jungle-C-Data-Structure/blob/master/Data-Structures/Linked_List/Q6_A_LL.c

Jungle-C-Data-Structure/Data-Structures/Linked_List/Q6_A_LL.c at master · yeooonee/Jungle-C-Data-Structure

 

 

 

 

문제풀이

while 문 안에서 가장 큰 값을 찾고, 값을 다 찾아서 더 이상 갈 곳이 없으면 현재의 max 값을 옮기는 작업을 실행했다. max 값을 찾는데 큰 어려움은 없었고, 값을 서로 변경하고, 끊어주고, 연결하는 것이서 꽤 헤맸다. 처음에 자리를 바꿔주는 것으로 생각했는데, 문제를 다시 읽어보니 맨 앞으로만 옮겨주는 것이었다.

 

// 1. max 값 찾기
// 2. Head 값을 바꿀때 어떤 값끼리 변경할지
// 3. 이미 max 값이 head 일 때 어떻게 처리할지 
int moveMaxToFront(ListNode **ptrHead)
{
    ListNode *cur;
	ListNode *max; //node, idx, 
	ListNode *val;
	ListNode *prev = NULL;
	ListNode *before_head, *before_max_next;
	int idx, max_value;
	
	max = *ptrHead; // 현재 head node 가 들어감 
	max_value = (*max).item;

	cur = *ptrHead;

	// 큰 값 찾기 
	while (true){
		// 더이상 갈 값이 때 현재 max 값 반환
		if ((*cur).next == NULL){
			if (prev){	// prev 가 있을때만

				// Head 값 max 의 node 주소로 변경
				before_head = *ptrHead; // head 의 주소 임시 변수에 저장
				*ptrHead = max;

				// prev 의 next 값 max 의 기존 next 로 변경 
				prev->next = max->next;

				// max 의 next 주소 Head 값으로 변경
				max->next = before_head;

			}
			break;
		}
		// max 값 변경
		if ((*cur).next->item > max_value){
			max_value = (*cur).next->item;
			max = (*cur).next;
			prev = cur;
		}
		cur = (*cur).next;
	}
}

 

 

값 변경에 대한 주요 로직만 살펴보면, Head 값을 max 값의 주소로 변경해준다. 이때, 기존 Head 값은 임시 변수에 보관해준다.

				// Head 값 max 의 node 주소로 변경
				before_head = *ptrHead; // head 의 주소 임시 변수에 저장
				*ptrHead = max;

 

 

기존 max 위치 의 앞에 있는 값을 max 의 뒷 값과 연결해준다.

				// prev 의 next 값 max 의 기존 next 로 변경 
				prev->next = max->next;

 

 

max 의 next 를 기존 head 값으로 변경해준다.

				// max 의 next 주소 Head 값으로 변경
				max->next = before_head;

 

 

그림으로 그리면 아래와 같다.

 

 

 

어려웠던 점

1. 이중 포인터에 대한 개념이 어려웠다. 
2. max 값을 가장 앞으로 뺐을 때, 연결 리스트끼리 어떻게 연결해야할 지에 대한 사고 과정이 어려웠다.

 

C 언어 주요 내용 정리