GaGe

알고리즘 과제 PA3 본문

알고리즘/[2020] 알고리즘 과제

알고리즘 과제 PA3

Sorrel 2021. 1. 9. 16:05
#include <iostream>
#include <cstring>
#include "concat.h"
using namespace std;

concat::concat(void){
	this->num = 0;
	this->pa = 0;
	return;
}

concat::concat(int* priority, char **words, int n){
	int i=0;
	this->num = n;
	this->pa = new pri* [n];
	for(i=0;i<n;i++)	this->pa[i] = new pri(priority[i], words[i]); 
	return;
}

concat::~concat(void){
	if(this->pa){
		int i=0, n = this->num;
		for(i=0;i<n;i++)	if(this->pa[i])		delete this->pa[i];
		delete[] this->pa;
	}
	return;
}

char* concat::concatenate(void){
    int k = 0;
    for(int i =0; i<num ; i++){
        if((this->pa[i]->pr)>k){
            k=this->pa[i]->pr;
        }
    }
    int *tmp = new int[k+1];
    for(int i=0; i<k+1;i++){
         tmp[i]=0;
    }
    for(int j = 0; j<num; j++){
        tmp[this->pa[j]->pr]+=1;
    }
    for(int i=1; i<k+1; i++){
        tmp[i]+=tmp[i-1];
    }
    int* index = new int[num];
    for(int j = num-1; j>=0; j--){
        tmp[this->pa[j]->pr]-=1;
        index[tmp[this->pa[j]->pr]]=j;
    }
    delete[] tmp;
    int str = 0;
    for(int i =0; i<num; i++){
        if(index[i]<(num/2)){
            str=str+1;
        }
        else{
            str=str+strlen(this->pa[index[i]]->word);
        }
    }
    str=str+(num-1);
    char* result= new char[str+1];
    result[0]=0;
    char src[]="-";
    char space[]= " ";
    int size=0;
    for(int i = 0 ; i<num; i++){
        if(index[i]<(num/2)){
            memcpy(result+size, src, 1);
            size+=1;
            
        }
        else{
            memcpy(result+size,this->pa[index[i]]->word, strlen(this->pa[index[i]]->word));
            size+=strlen(this->pa[index[i]]->word);
        }
        if(i<num-1){
            memcpy(result+size, space,1);
            size+=1;

        }
    }
    result[size]=0;
    delete[] index;
	return result;
}

'알고리즘 > [2020] 알고리즘 과제' 카테고리의 다른 글

알고리즘 과제 PA4  (0) 2021.01.09
알고리즘 과제 PA2  (0) 2021.01.09
알고리즘 과제 PA1  (0) 2021.01.09
알고리즘 과제 PA5  (0) 2021.01.09
Comments