//Radix Sort
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
struct CounselingTime //한 학생의 상담 시간을 저장
{
int start; //상담 시작 시간
int end; //상담 종료 시간
};
const int studentNumberMax = 100000; //1 <= 학생 수 <= studentNumberMax
const int CounselingTimeMax = (int)pow((double)2, (double)31); // 0 <= 상담 시작 및 종료 시간의 최대값 <= CounselingTimeMax - 1
const int QueueNumber = 10; //10진수를 사용하므로 큐의 개수: 10개
const int DigitsNumber = 10; //상담 종료 시간의 최댓값의 자릿수: 10자리
void WriteCTL(int& SN, vector<struct CounselingTime>& CTL); //상담 시간 목록의 내용 작성(학생 수를 정하고 각 학생의 상담 시작 및 종료 시간 설정)
void RadixSort(vector<struct CounselingTime>& CTL, queue<struct CounselingTime> Bucket[]); //기수 정렬을 통해 상담 시간 목록의 각 학생의 상담 종료 시간이 오름차순이 되도록 정렬
void WriteCTT(vector<struct CounselingTime>& CTL, vector<struct CounselingTime>& CTT); // 상담 시간표의 내용 작성(최대한 많은 학생과 상담할 수 있는 상담 시간표 작성)
void showCTT(vector<struct CounselingTime>& CTT); //상담 학생 수와 상담 시간표를 출력
int main(int argc, char** argv)
{
clock_t programStart = clock(); //프로그램 시작 시간
clock_t sortStart; //정렬 시작 시간
clock_t sortEnd; //정렬 종료 시간
clock_t programEnd; //프로그램 종료 시간
int studentNumber; //전체 학생 수(SN)
vector<struct CounselingTime> CounselingTimeList; //상담 시간 목록. 모든 학생의 상담 시작 및 종료 시간을 저장(CTL)
vector<struct CounselingTime> CounselingTimeTable; //최대한 많은 학생과 상담할 수 있는 상담 시간표 저장(CTT)
queue<struct CounselingTime> Bucket[QueueNumber]; //기수 정렬을 위한 버킷
srand((unsigned int)time(NULL)); //난수 생성을 위한 코드
WriteCTL(studentNumber, CounselingTimeList); //상담 시간 목록의 내용 작성(상담 학생 수를 정하고 각 학생의 상담 시작 및 종료 시간 설정)
sortStart = clock(); //정렬 시작 시간
RadixSort(CounselingTimeList, Bucket);//기수 정렬을 통해 상담 시간 목록의 각 학생의 상담 종료 시간이 오름차순이 되도록 정렬
sortEnd = clock(); // 정렬 종료 시간
WriteCTT(CounselingTimeList, CounselingTimeTable); // 상담 시간표의 내용 작성(최대한 많은 학생과 상담할 수 있는 상담 시간표 작성)
showCTT(CounselingTimeTable); //상담 학생 수와 상담 시간표를 출력
programEnd = clock(); //프로그램 종료 시간
cout << "전체 학생 수: " << CounselingTimeList.size() << endl; //전체 학생 수 출력
cout << "상담 학생 수: " << CounselingTimeTable.size() << endl; //상담 학생 수 출력
cout << "프로그램 실행 시간: " << (double)(programEnd - programStart) / (double)1000 << endl; //프로그램 실행 시간 출력
cout << "정렬 실행 시간 :" << (double)(sortEnd - sortStart) / (double)1000 << endl; //정렬 실행 시간 출력
return 0;
}
void WriteCTL(int& SN, vector<struct CounselingTime>& CTL) //상담 시간 목록의 내용 작성(학생 수를 정하고 각 학생의 상담 시작 및 종료 시간 설정)
{
int studentNumber = rand() % studentNumberMax + 1; //학생 수를 1~studentNumberMax 사이의 값 중 하나로 랜덤 지정
for (int i = 0; i < studentNumber; i++) //각 학생의 상담 시작 및 종료 시간 설정
{
struct CounselingTime tmp;
tmp.start = rand() % CounselingTimeMax; //한 학생의 상담 시작 시간 저장
while (true)
{
tmp.end = rand() % CounselingTimeMax; //한 학생의 상담 종료 시간 저장
if (tmp.end >= tmp.start)
{
break; //한 학생의 상담 종료 시간 >= 상담 시작 시간이면 정상적인 시간 저장이므로 루프 종료
}
}
CTL.push_back(tmp); //한 학생의 상담 시간을 상담 시간 목록에 저장
}
/* 전체 학생 수도 가장 많고 상담 종료 시간도 내림차순으로 설정되어 있는 최악의 경우 계산용으로 쓰일 상담 시간 목록 작성
int studentNumber = studentNumberMax; //학생 수를 studentNumberMax로 지정
for (int i = 0; i < studentNumber; i++) //각 학생의 상담 시작 및 종료 시간 설정
{
//상담 시작 및 종료 시간을 최댓값부터 1씩 줄여나가며 저장
int tmpTime = CounselingTimeMax - 1;
struct CounselingTime tmp;
tmp.start = tmpTime;
tmp.end = tmpTime;
tmpTime++;
CTL.push_back(tmp); //한 학생의 상담 시간을 상담 시간 목록에 저장
}
*/
}
void RadixSort(vector<struct CounselingTime>& CTL, queue<struct CounselingTime> Bucket[])//기수 정렬을 통해 상담 시간 목록의 각 학생의 상담 종료 시간이 오름차순이 되도록 정렬
{
for (unsigned int i = 0; i < DigitsNumber; i++) //상담 종료 시간의 최댓값의 자릿수만큼 반복
{
for (unsigned int j = 0; j < CTL.size(); j++) //상담 시간 목록의 학생 수만큼 반복
{
//상담 종료 시간의 뒤에서 (i + 1)번째 자릿수를 구함
int digit = CTL[j].end;
for (int k = 0; k < i; k++)
{
digit /= 10;
}
digit %= 10;
//상담 종료 시간의 뒤에서 (i + 1)번째 자릿수의 값(0~9)에 따라
//버킷의 알맞은 큐(0~9)에 넣음
switch (digit)
{
case 0:
Bucket[i].push(CTL[j]);
break;
case 1:
Bucket[i].push(CTL[j]);
break;
case 2:
Bucket[i].push(CTL[j]);
break;
case 3:
Bucket[i].push(CTL[j]);
break;
case 4:
Bucket[i].push(CTL[j]);
break;
case 5:
Bucket[i].push(CTL[j]);
break;
case 6:
Bucket[i].push(CTL[j]);
break;
case 7:
Bucket[i].push(CTL[j]);
break;
case 8:
Bucket[i].push(CTL[j]);
break;
case 9:
Bucket[i].push(CTL[j]);
break;
}
}
int bucketNumber = 0; //버킷에서 bucketNumber번째 큐를 방문함
for (unsigned int j = 0; j < CTL.size(); j++) //상담 시간 목록의 학생 수만큼 반복
{
if (Bucket[bucketNumber].empty() == true)
{
//버킷에서 지금 보고 있는 큐가 비었다면 다음 큐로 넘어감
bucketNumber++;
continue;
}
//버킷에서 지금 보고 있는 큐의 맨앞에 있는 학생의 상담 시간 정보를 빼내고
//상담 시간 목록의 j번째 인덱스의 값으로 함
CTL[j] = Bucket[bucketNumber].front();
Bucket[bucketNumber].pop();
}
}
}
void WriteCTT(vector<struct CounselingTime>& CTL, vector<struct CounselingTime>& CTT) // 상담 시간표의 내용 작성(최대한 많은 학생과 상담할 수 있는 상담 시간표 작성)
{
CTT.push_back(CTL[0]); //상담 시간 목록의 가장 처음의 내용을 상담 시간표에 추가
for (unsigned int i = 1; i < CTL.size(); i++) //상담 시간 목록의 내용을 1번 인덱스부터 마지막 인덱스까지 살펴봄
{
if (CTL[i].start >= CTT.back().end)
{
/*
상담 시간 목록 i번 인덱스의 상담 시작 시간이 상담 시간표의 마지막 상담 종료 시간보다 이르지 않으면
상담 시간표에 상담 시간 목록 i번 인덱스의 내용 추가
*/
CTT.push_back(CTL[i]);
}
}
return;
}
void showCTT(vector<struct CounselingTime>& CTT) //상담 학생 수와 상담 시간표를 출력
{
cout << "상담 학생 수: " << CTT.size() << "명" << endl;
cout << "<상담 시간표>" << endl;
for (unsigned int i = 0; i < CTT.size(); i++)
{
cout << "(" << CTT[i].start << ", " << CTT[i].end << ")" << endl;
}
cout << endl;
return;
}