imported>Unknown at 05:30, 7 February 2021

2021-02-07T05:30:21Z

New page

== 풀이 ==
== 숙제 ==
#include <iostream>
using namespace std;
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>

ifstream fin("test.txt");

struct Data
{
string data;
int p;
float priority;
bool operator() (const Data* a, const Data* b)
{
if (a->data < b->data)
return true;
return false;
}
};

struct Node
{
string data;
int p;
int level;
Node* left;
Node* right;
};

vector <Data*> indata;
Node* root;
int sum;

bool compare(const Data* a, const Data* b)
{
if (a->priority > b->priority)
return true;
return false;
}

void input()
{
int number;
fin >> number;

Data* d;
string data;
int p;
indata.reserve(number);

for (int i = 0; i < number; i++)
{
fin >> data >> p;
d = new Data();
d->data = data;
d->p = p;
indata.push_back(d);
}
}

void insertNode(int i)
{
Node * newNode = new Node();
newNode->data = indata[i]->data;
newNode->p = indata[i]->p;
newNode->left = newNode->right = NULL;

int l = 1;
Node * temp = root;
Node * parent = NULL;
while (temp)
{
l++;
parent = temp;
if (temp->data < newNode->data)
temp = temp->right;
else if (temp->data > newNode->data)
temp = temp->left;
else
return;
}
if (parent)
{
if (parent->data < newNode->data)
parent->right = newNode;
else
parent->left = newNode;
}
else
root = newNode;
newNode->level = l;
}

void makeTree()
{
root = NULL;
for (int i = 0; i < indata.size(); i++)
insertNode(i);
}

void inorder(Node* t)
{
if (t->left)
inorder(t->left);
cout << t->data << " ";
sum = sum + t->level * t->p;
if (t->right)
inorder(t->right);
}

void show()
{
sum = 0;
inorder(root);
cout << "\n총 cost : " << sum << endl;
}

void priorPrioritySet(int left, int right, int p)
{
if (left >= right)
return;
indata[(left + right) / 2]->priority = p;
priorPrioritySet(left, (left + right) / 2, p - 41);
priorPrioritySet((left+right) / 2 + 1, right, p - 41);
}

void process()
{
sort(indata.begin(),indata.end(),Data());
int size = indata.size();
priorPrioritySet(0, size-1, 0);
float middle = size / 2.0;
// for (int i = 0; i < size; i++)
// indata[i]->priority += (float)indata[i]->p;
sort(indata.begin(),indata.end(),compare);
makeTree();
show();
}

int main()
{
input();
process();
return 0;
}
----
[[알고리즘8주숙제]]

알고리즘8주숙제/문보창 - Revision history

imported>Unknown at 05:30, 7 February 2021