안녕하세요 C++ 공부하고있는 대학생입니다.
이번에도 저번에 이어서, 정올 1번수준 codeup 사이트 4721번 문제를 정리해보려고 합니다.
문제1) 투표
N 명의 학생들이 모인 초등학교 반에서 학급회장 선거를 하려고 한다. 그 중 3명이 회장후보로 나왔고, 이들에 대한 선호도를 N 명의 학생들 각각에게 적어내도록 하였다. 세 명의 후보는 후보 1번, 후보 2번, 후보 3번이라 한다.
모든 학생은 3명의 후보 중에서 가장 선호하는 후보에게는 3점, 두 번째로 선호하는 후보에게는 2점, 가장 선호하지 않는 후보에게는 1점을 주어야 한다. 3명의 후보에 대한 한 학생의 선호 점수는 모두 다르며, 1점, 2점, 3점이 정확히 한 번씩 나타나야 한다.
후보의 최종 점수는 학생들로부터 받은 자신의 선호도 점수를 모두 더한 값이 된다. 그러면 3명의 후보 중 가장 큰 점수를 받은 후보가 회장으로 결정된다. 단, 점수가 가장 큰 후보가 여러 명인 경우에는 3점을 더 많이 받은 후보를 회장으로 결정하고, 3점을 받은 횟수가 같은 경우에는 2점을 더 많이 받은 후보를 회장으로 결정한다. 그러나 3점과 2점을 받은 횟수가 모두 동일하면, 1점을 받은 횟수도 같을 수밖에 없어 회장을 결정하지 못하게 된다.
입력
입력 파일의 첫째 줄에는 반의 학생들의 수 N (3<=N<=1,000) 이 주어진다. 다음 N 개의 각 줄에는 각 학생이 제출한 회장후보 3명에 대한 선호 점수가 주어지는 데, 첫 번째 점수는 후보 1번에 대한 점수이고 두 번째 점수는 후보 2번에 대한 점수이고 세 번째 점수는 후보 3번에 대한 점수이다. 이 세 점수는 서로 다르며, 1, 2, 3이 정확히 한 번씩 나타난다.
출력
학생들의 선호도 투표 결과로부터, 회장이 유일하게 결정되는 경우에는 회장으로 결정된 후보의 번호와 최고 점수를 출력하고, 유일하게 결정할 수 없는 경우에는 0과 최고 점수를 출력한다.
입력 예시
6
3 1 2
2 3 1
3 1 2
1 2 3
3 1 2
1 2 3
출력 예시
1 13
먼저 제 소스코드를 보여드리겠습니다.
#include <stdio.h>
#include <stdlib.h>
int oneCheck = 0;
int twoCheck = 0;
int threeCheck = 0;
int index = 0;
int onecount[3];
int twocount[3];
int threecount[3];
int black = 0;
typedef struct node {
int one;
int two;
int three;
struct node* next;
}node;
typedef struct checknode {
int total;
int checkindex;
int checkThree;
int checkTwo;
struct checknode* next;
struct checknode* prev;
}checknode;
typedef struct List {
struct node* head;
struct checknode* tail;
int count;
int count2;
}List;
List* init() {
List* list = (List*)malloc(sizeof(List));
if (list == NULL) {
printf("err\n");
}
else {
list->head = NULL;
list->tail = NULL;
list->count = 0;
list->count2 = 0;
return list;
}
}
void insert(List *list, int data1, int data2, int data3) {
node* newNode = (node*)malloc(sizeof(node));
node* preNode = list->head;
newNode->one = data1;
newNode->two = data2;
newNode->three = data3;
if (list->count == 0) {
newNode->next = newNode;
list->head = newNode;
list->count++;
}
else {
for (int i = 0; i < list->count; i++) {
preNode = preNode->next;
}
newNode->next = preNode->next;
preNode->next = newNode;
list->count++;
}
}
void checking(List* list,int *check) {
node* curNode = list->head;
if (list->count == 0) return;
else {
oneCheck += list->head->one;
twoCheck += list->head->two;
threeCheck += list->head->three;
check[0] = oneCheck;
check[1] = twoCheck;
check[2] = threeCheck;
list->head = list->head->next;
list->count--;
free(curNode);
checking(list,check);
}
}
void insert2(List* list,int *check) {
checknode* newCheck = (checknode*)malloc(sizeof(checknode));
checknode* preCheck = list->tail;
newCheck->checkindex = index + 1;
newCheck->checkThree = threecount[index];
newCheck->checkTwo = twocount[index];
newCheck->total = check[index];
if (list->count2 == 0) {
newCheck->next = newCheck;
newCheck->prev = newCheck;
list->tail = newCheck;
list->count2++;
index++;
}
else {
for (int i = 0; i < list->count2; i++) {
preCheck = preCheck->next;
}
newCheck->next = preCheck->next;
newCheck->prev = preCheck;
preCheck->next = newCheck;
newCheck->next->prev = newCheck;
list->count2++;
index++;
}
}
void print(List* list) {
int i;
printf("???? %d\n", list->count2);
for (i = 0, list->tail; i < list->count2; i++, list->tail = list->tail->prev) {
printf("index : %d\n", list->tail->checkindex);
printf("total : %d\n", list->tail->total);
printf("threecount : %d\n", list->tail->checkThree);
printf("twocount : %d\n", list->tail->checkTwo);
}
}
void resultchecking(List* list) {
checknode* curCheck = list->tail;
checknode* nextCheck = list->tail->prev;
if (list->count2 == 0) return;
else {
if (curCheck->total < nextCheck->total) {
list->tail = nextCheck;
}
else if (curCheck->total == nextCheck->total) {
if (curCheck->checkThree > nextCheck->checkThree) {
list->tail = curCheck;
black = 0;
}
else if (curCheck->checkThree < nextCheck->checkThree) {
list->tail = nextCheck;
black = 0;
}
else {
if (curCheck->checkTwo > nextCheck->checkTwo) {
list->tail = curCheck;
black = 0;
}
else if (curCheck->checkTwo < nextCheck->checkTwo) {
list->tail = nextCheck;
black = 0;
}
else {
black++;
if (list->count2 > 1) list->tail = list->tail->next;
}
}
}
list->count2--;
resultchecking(list);
}
}
int main() {
int countcheck = 0;
int one, two, three;
List* list = init();
int* check = (int*)malloc(sizeof(int) * 3);
for (int i = 0; i < 3; i++) {
onecount[i] = 0;
twocount[i] = 0;
threecount[i] = 0;
check[i] = 0;
}
scanf("%d", &countcheck);
for (int i = 0; i < countcheck; i++) {
scanf("%d %d %d", &one, &two, &three);
if (one == 3) threecount[0] = threecount[0]+1;
else if (one == 2) twocount[0] = twocount[0]+1;
else onecount[0] = onecount[0] + 1;
if (two == 3) threecount[1] = threecount[1] + 1;
else if (two == 2) twocount[1] = twocount[1] + 1;
else onecount[1] = onecount[1] + 1;
if (three == 3) threecount[2] = threecount[2] + 1;
else if (three == 2) twocount[2] = twocount[2] + 1;
else onecount[2] = onecount[2] + 1;
insert(list, one, two, three);
}
checking(list,check);
for (int i = 0; i < 3; i++) {
insert2(list, check);
}
resultchecking(list);
if (black != 0) {
printf("0 %d", list->tail->total);
}
else {
printf("%d %d", list->tail->checkindex, list->tail->total);
}
for(int i = 0; i<3; i++) {
checknode *returnNode = list->tail;
list->tail = list->tail->next;
free(returnNode);
}
free(list);
return 0;
}3점 2점 1점에 대한 각각의 수를 넣어주는 3개공간의 배열을 선언하였고, for문을 통해 배열에 수를 넣어주었습니다.
그리고 insert 사용자 정의함수로 1번째 연결리스트 안에 각각의 사람이 후보자에게 준 점수를 넣어주었습니다.
그 다음 checking 사용자 정의함수에 1번째 연결리스트에 있는 각각의 사람이 각각의 후보에게 준 점수를 체크하여 check배열에 넣어 준 후, free로 1번째 연결리스트를 모두 반환하였습니다.
그리고 2번째연결리스트에 check 배열에 있는 각각 후보의 점수를 넣고, 2번째연결리스트에 후보에 대한 index 부여, total 점수, 3점 2점에 대한 카운터에 대한 데이터를 넣어주었습니다.
그리고 resultchecking 함수를 통해 문제 조건에서 가장 큰 점수를 가진사람이 tail 노드가 되도록 잡았습니다. 이때 동점자가 있을경우, 3점의 갯수, 2점의갯수를 모두 비교하였습니다.
그리고 동점자가 있을경우 3점과 2점의 수를 비교하여 많은쪽이 tail점이 될 수 있도록 잡았고, 누가 당선자인지 모를경우에는 black 변수를 하나 증가시켜서 0과 최대점수를 출력하도록 설정하였습니다.
당선자가 있을경우에는 해당 당선자에 대한 인덱스와 최고점수를 출력하게 하였고,
마지막에 2번째연결리스트와 list 구조체에 대한 동적할당을 반환 해 줍니다.
이 문제는 예외에 대한 처리가 상당히 힘들었던 문제였습니다. 그래도 어떻게든 풀 수 있을정도의 난이도인 문제여서 많은 고민을해서 풀어보았습니다.
