KU COSE101 2016기말고사 5번 문제

2016 기출	1번	2번	3번	4번	5번
2017 기출	1번	2번	3번	4번	5번
2018 기출	1번	2번	3번	4번	5번	6번

main 함수에서는 선수의 수 n과 각 선수의 ID와 점수를 제공합니다.

Linked list의 head는 main함수에 선언되어 있으며, head->nextPtr = NULL 입니다.

가장 높은 득점을 올린 선수를 MVP로 선출하고자 한다. 선수의 ID와 득점은 다음과 같이 주어진 구조를 이용하여 linked list로 관리한다.

struct player{
  int id_number;
  int scores;
  struct player* nextPtr;
};

사용자 자료형과 함수가 다음과 같이 정의되어 있다고 가정하자.

//synonyms for the stucture and pointer to it
typedef struct player Player;
typedef Player *PlayerPtr;
//function prototype
void insert(PlayerPtr *sPtr, int id, int value);
void announce_MVP(PlayerPtr *sPtr);

(a) 아래 insert함수의 내용을 작성하시오. 이 함수는 (1) 새로운 선수를 위한 노드를 생성하고, (2) 이 선수의 득점을 기록한 후, (3) 주어진 linked list에 점수의 값이 작은 값에서 큰 값으로 정렬되도록 삽입한다. 선수의 ID와 점수는 main함수에서 전달된다고 가정하고 이 프로그램의 실행을 위한 memory는 충분하다고 가정한다.

//sPtr points to the linked list starting address, id and value
//are formal parameters for player's ID number and scores
void insert(PlayerPtr *sPtr, int id, int value) {

}

(b) 아래 announce_MVP 함수를 작성하시오. 이 함수는 (1) 모든 MVP 선수를 찾아 (다수인 경우), (2) 이들의 ID와 점수를 출력하고, (3) 해당되는 노드를 list에서 삭제한다. 선수는 총 10명이라고 가정하고 linked list는 임의의 순서로 생성되었다고 가정한다.

예를 들어, 다음과 같은 linked list를 갖고 있다고 가정하면

(ID:5, Score:18) --> (ID:9, Score:21) --> (ID:11, Score:17) --> (ID:23, Score:21) --> NULL

announce_MVP함수는 다음의 내용을 출력하여야 한다.

9, 21
23, 21

void announce_MVP(PlayerPtr *sPtr) {
  //find the MVP players
  
  //print MVP players' information and delete them from the linked list
  
}

---

예시답안

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

struct player{
	int id_number;
	int scores;
	struct player* nextPtr;
};

typedef struct player Player;
typedef Player *PlayerPtr;

void insert(PlayerPtr *sPtr, int id, int value);
void announce_MVP(PlayerPtr *sPtr);

int main()
{
	int n,i,id,sc;
	PlayerPtr head = (PlayerPtr)malloc(sizeof(Player));
	head->nextPtr = NULL;
	scanf("%d",&n);
	for(i=0 ; i<n ; i++){
		scanf("%d %d",&id,&sc);
		insert(&head, id, sc);
	}
	announce_MVP(&head);
}

void insert(PlayerPtr *sPtr, int id, int value) {
	PlayerPtr prevPtr = *sPtr;
	PlayerPtr curPtr = *sPtr;
	PlayerPtr newPtr = (PlayerPtr)malloc(sizeof(Player));
	
	newPtr->id_number = id;
	newPtr->scores = value;
	newPtr->nextPtr = NULL;
	
	while(curPtr != NULL) {
		if(curPtr->nextPtr == NULL){
			curPtr->nextPtr = newPtr;
			break;
		}
		if(curPtr->scores > value) {
			prevPtr->nextPtr = newPtr;
			newPtr->nextPtr = curPtr;
			break;
		}
		prevPtr = curPtr;
		curPtr = curPtr->nextPtr;
	}
}

void announce_MVP(PlayerPtr *sPtr) {
	int high = -1;
	PlayerPtr curPtr = (*sPtr)->nextPtr;
	while(curPtr != NULL) {
		if(curPtr->scores > high) high = curPtr->scores;
		curPtr = curPtr->nextPtr;
	}
	PlayerPtr prevPtr = (*sPtr);
	curPtr = (*sPtr)->nextPtr;
	while(curPtr != NULL){
		if(curPtr->scores == high) {
			printf("%d %d\n",curPtr->id_number, curPtr->scores);
			prevPtr->nextPtr = curPtr->nextPtr;
			free(curPtr);
			curPtr = prevPtr->nextPtr;
		}
		else{
			prevPtr->nextPtr = curPtr;
			curPtr = curPtr->nextPtr;
		}
	}
}