FromDuskTillDawn/조현태 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:03Z

Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:17Z

New page

== [[FromDuskTillDawn/조현태]] ==
=== 감상 및 설명 ===
불쌍한 뱀파이어..T.T
나이가 들어도 밤에 밖에 못다니다니.. 이동네는 아템빨도 없나??ㅎㅎ

일단 수많은 귀차니즘으로 약간의 전역변수를 사용하였으며..
문제에서 처럼 여러개의 테스트 케이스도 받도록 수정하였다.

참고 : 나름대로 약간의 최적화가 되어있다. 그러나~ vector가 아닌 list를 사용한다면 좀더 효과적일듯하다.ㅎ 이런 귀차니즘~
=== 소스코드 ===
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const char DEBUG_READ[] = "2\n3\nUlm Muenchen 17 2\nUlm Muenchen 19 12\nUlm Muenchen 5 2\nUlm Muenchen\n10\nLugoj Sibiu 12 6\nLugoj Sibiu 18 6\nLugoj Sibiu 24 5\nLugoj Medias 22 8\nLugoj Medias 18 8\nLugoj Reghin 17 4\nSibiu Reghin 19 9\nSibiu Medias 20 3\nReghin Medias 20 4\nReghin Bacau 24 6\nLugoj Bacau";

const int BUFFER_SIZE = 255;

#define TRUE 1
#define FALSE 0

struct STown
{
STown(const char* inputName)
{
name = inputName;
}
string name;
vector<STown*> nextTown;
vector<int> startTime;
vector<int> timeDelay;
};

vector<STown*> g_myTowns;
string g_suchStartTown;
string g_suchEndTown;
int g_minimumDelayTime = 0;

STown* SuchOrAddTown(const char* townName)
{
for (register unsigned int i = 0; i < g_myTowns.size(); ++i)
{
if (g_myTowns[i]->name == townName)
return g_myTowns[i];
}
g_myTowns.push_back(new STown(townName));
return g_myTowns[g_myTowns.size() - 1];
}

const char* Parser(const char* readData)
{
char startStationName[BUFFER_SIZE];
char endStationName[BUFFER_SIZE];
int startTime;
int delayTime;
int sizeOfTimeTable;

sscanf(readData, "%d", &sizeOfTimeTable);
readData = strchr(readData, '\n') + 1;
for(register int i = 0; i < sizeOfTimeTable; ++i)
{
sscanf(readData, "%s %s %d %d", startStationName, endStationName, &startTime, &delayTime);

STown* thisStation = SuchOrAddTown(startStationName);
thisStation->nextTown.push_back(SuchOrAddTown(endStationName));
thisStation->startTime.push_back(startTime % 24);
thisStation->timeDelay.push_back(delayTime);

readData = strchr(readData, '\n') + 1;
}
sscanf(readData, "%s %s", startStationName, endStationName);
g_suchStartTown = startStationName;
g_suchEndTown = endStationName;
readData = strchr(readData, '\n');

if (NULL != readData)
return readData + 1;
else
return NULL;
}

bool isDeadTime(int inputTime)
{
if (18 > inputTime % 24 && 6 < inputTime % 24)
return TRUE;
return FALSE;
}

void SuchTown(STown* startTown, STown* endTown)
{
//// 시작 준비 ////
vector< vector<STown*> > allSuchList;
vector<int> allDelay;
vector<STown*> newTown;
int newAddPoint;
newTown.push_back(startTown);
allDelay.push_back(0);
allSuchList.push_back(newTown);

do{
//// 가장 시간이 낮은 경우에 대해서 연산을 수행합니다. ////
newAddPoint = allSuchList[0].size() - 1;
STown* suchTown = allSuchList[0][allSuchList[0].size() - 1];
for (register int i = 0; i < (int)(suchTown->nextTown.size()); ++i)
{
if (suchTown->timeDelay[i] <= 12 && !(isDeadTime(suchTown->startTime[i]) || isDeadTime(suchTown->startTime[i] + suchTown->timeDelay[i])))
{
vector<STown*> suchTownList = allSuchList[0];
suchTownList.push_back(suchTown->nextTown[i]);
allSuchList.push_back(suchTownList);

if (allDelay[0] % 24 <= suchTown->startTime[i])
allDelay.push_back(allDelay[0] + suchTown->startTime[i] - (allDelay[0] % 24) + suchTown->timeDelay[i]);
else
allDelay.push_back(allDelay[0] + (suchTown->startTime[i] + 24) - (allDelay[0] % 24) + suchTown->timeDelay[i]);

if (g_suchEndTown == suchTown->nextTown[i]->name)
{
if ((0 != g_minimumDelayTime && g_minimumDelayTime > allDelay[allDelay.size() - 1]) || 0 == g_minimumDelayTime)
g_minimumDelayTime = allDelay[allDelay.size() - 1];
}
}
}
allSuchList.erase(allSuchList.begin());
allDelay.erase(allDelay.begin());
//// 동일한 위치로 간것과 전체 시간을 초과한 것을 삭제합니다. ////
for (register int i = newAddPoint; i < (int)allSuchList.size(); ++i)
{
if (0 != g_minimumDelayTime && g_minimumDelayTime < allDelay[i])
{
allSuchList.erase(allSuchList.begin() + i);
allDelay.erase(allDelay.begin() + i);
}
else
{
bool isSame = FALSE;
for (register int j = 0; j < (int)allSuchList[i].size(); ++j)
{
for (register int k = j + 1; k < (int)allSuchList[i].size(); ++k)
{
if (allSuchList[i][j] == allSuchList[i][k])
{
allSuchList.erase(allSuchList.begin() + i);
allDelay.erase(allDelay.begin() + i);
--i;
isSame = TRUE;
break;
}
}
if (isSame)
break;
}

}
}

if (0 == allSuchList.size())
break;
//// 가장 시간이 낮은 경우를 제일 앞으로 둡니다. ////
int minimumDelayPoint = 0;
int minimumDelay = allDelay[0];
for (register int i = 1; i < (int)allSuchList.size(); ++i)
{
if (minimumDelay > allDelay[i])
{
minimumDelay = allDelay[i];
minimumDelayPoint = i;
}
}
allDelay[minimumDelayPoint] = allDelay[0];
vector<STown*> bufferSTown = allSuchList[minimumDelayPoint];
allDelay[0] = minimumDelay;
allSuchList[0] = bufferSTown;
}while(0 != allSuchList.size());
}

void freeMemory()
{
for (register int i = 0; i < (int)g_myTowns.size(); ++i)
delete g_myTowns[i];
}

void main()
{
int numberOfTestCase = 0;
const char* readData = DEBUG_READ;
sscanf(readData, "%d", &numberOfTestCase);
readData = strchr(readData, '\n') + 1;
for (register int i = 0; i < numberOfTestCase; ++i)
{
//// 초기화 ////
g_myTowns.clear();
g_suchStartTown.clear();
g_suchEndTown.clear();
g_minimumDelayTime = 0;

//// 연산 ////
readData = Parser(readData);
SuchTown(SuchOrAddTown(g_suchStartTown.c_str()), SuchOrAddTown(g_suchEndTown.c_str()));
freeMemory();
if (0 == g_minimumDelayTime)
cout << "There is no route Vladimir can take." << endl;
else
cout << "Vladimir needs " << g_minimumDelayTime / 24 << " litre(s) of blood. " << endl;
}
}
----
[[FromDuskTillDawn]]

← Older revision		Revision as of 00:16, 27 March 2026
Line 15:		Line 15:
	using namespace std;		using namespace std;

	const char DEBUG_READ[] = "2\n3\nUlm Muenchen 17 2\nUlm Muenchen 19 12\nUlm Muenchen 5 2\nUlm Muenchen\n10\nLugoj Sibiu 12 6\nLugoj Sibiu 18 6\nLugoj Sibiu 24 5\nLugoj Medias 22 8\nLugoj Medias 18 8\nLugoj Reghin 17 4\nSibiu Reghin 19 9\nSibiu Medias 20 3\nReghin Medias 20 4\nReghin Bacau 24 6\nLugoj Bacau";		const char DEBUG_READ[] = "2\n3\nUlm Muenchen 17 2\nUlm Muenchen 19 12\nUlm Muenchen 5 2\nUlm Muenchen\n10\nLugoj Sibiu 12 6\nLugoj Sibiu 18 6\nLugoj Sibiu 24 5\nLugoj Medias 22 8\nLugoj Medias 18 8\nLugoj Reghin 17 4\nSibiu Reghin 19 9\nSibiu Medias 20 3\nReghin Medias 20 4\nReghin Bacau 24 6\nLugoj Bacau";

	const int BUFFER_SIZE = 255;		const int BUFFER_SIZE = 255;
Line 43:		Line 43:
	for (register unsigned int i = 0; i < g_myTowns.size(); ++i)		for (register unsigned int i = 0; i < g_myTowns.size(); ++i)
	{		{
	if (g_myTowns[i]->name == townName)		if (g_myTowns[i]->name == townName)
	return g_myTowns[i];		return g_myTowns[i];
	}		}
	g_myTowns.push_back(new STown(townName));		g_myTowns.push_back(new STown(townName));
	return g_myTowns[g_myTowns.size() - 1];		return g_myTowns[g_myTowns.size() - 1];
	}		}

	const char* Parser(const char* readData)		const char* Parser(const char* readData)
	{		{
	char startStationName[BUFFER_SIZE];		char startStationName[BUFFER_SIZE];
	char endStationName[BUFFER_SIZE];		char endStationName[BUFFER_SIZE];
	int startTime;		int startTime;
	int delayTime;		int delayTime;
Line 102:		Line 102:
	do{		do{
	//// 가장 시간이 낮은 경우에 대해서 연산을 수행합니다. ////		//// 가장 시간이 낮은 경우에 대해서 연산을 수행합니다. ////
	newAddPoint = allSuchList[0].size() - 1;		newAddPoint = allSuchList[0].size() - 1;
	STown* suchTown = allSuchList[0][allSuchList[0].size() - 1];		STown* suchTown = allSuchList[0][allSuchList[0].size() - 1];
	for (register int i = 0; i < (int)(suchTown->nextTown.size()); ++i)		for (register int i = 0; i < (int)(suchTown->nextTown.size()); ++i)
	{		{
	if (suchTown->timeDelay[i] <= 12 && !(isDeadTime(suchTown->startTime[i]) \|\| isDeadTime(suchTown->startTime[i] + suchTown->timeDelay[i])))		if (suchTown->timeDelay[i] <= 12 && !(isDeadTime(suchTown->startTime[i]) \|\| isDeadTime(suchTown->startTime[i] + suchTown->timeDelay[i])))
	{		{
	vector<STown*> suchTownList = allSuchList[0];		vector<STown*> suchTownList = allSuchList[0];
	suchTownList.push_back(suchTown->nextTown[i]);		suchTownList.push_back(suchTown->nextTown[i]);
	allSuchList.push_back(suchTownList);		allSuchList.push_back(suchTownList);

	if (allDelay[0] % 24 <= suchTown->startTime[i])		if (allDelay[0] % 24 <= suchTown->startTime[i])
	allDelay.push_back(allDelay[0] + suchTown->startTime[i] - (allDelay[0] % 24) + suchTown->timeDelay[i]);		allDelay.push_back(allDelay[0] + suchTown->startTime[i] - (allDelay[0] % 24) + suchTown->timeDelay[i]);
	else		else
	allDelay.push_back(allDelay[0] + (suchTown->startTime[i] + 24) - (allDelay[0] % 24) + suchTown->timeDelay[i]);		allDelay.push_back(allDelay[0] + (suchTown->startTime[i] + 24) - (allDelay[0] % 24) + suchTown->timeDelay[i]);

	if (g_suchEndTown == suchTown->nextTown[i]->name)		if (g_suchEndTown == suchTown->nextTown[i]->name)
	{		{
	if ((0 != g_minimumDelayTime && g_minimumDelayTime > allDelay[allDelay.size() - 1]) \|\| 0 == g_minimumDelayTime)		if ((0 != g_minimumDelayTime && g_minimumDelayTime > allDelay[allDelay.size() - 1]) \|\| 0 == g_minimumDelayTime)
	g_minimumDelayTime = allDelay[allDelay.size() - 1];		g_minimumDelayTime = allDelay[allDelay.size() - 1];
	}		}
	}		}
Line 129:		Line 129:
	for (register int i = newAddPoint; i < (int)allSuchList.size(); ++i)		for (register int i = newAddPoint; i < (int)allSuchList.size(); ++i)
	{		{
	if (0 != g_minimumDelayTime && g_minimumDelayTime < allDelay[i])		if (0 != g_minimumDelayTime && g_minimumDelayTime < allDelay[i])
	{		{
	allSuchList.erase(allSuchList.begin() + i);		allSuchList.erase(allSuchList.begin() + i);
Line 137:		Line 137:
	{		{
	bool isSame = FALSE;		bool isSame = FALSE;
	for (register int j = 0; j < (int)allSuchList[i].size(); ++j)		for (register int j = 0; j < (int)allSuchList[i].size(); ++j)
	{		{
	for (register int k = j + 1; k < (int)allSuchList[i].size(); ++k)		for (register int k = j + 1; k < (int)allSuchList[i].size(); ++k)
	{		{
	if (allSuchList[i][j] == allSuchList[i][k])		if (allSuchList[i][j] == allSuchList[i][k])
	{		{
	allSuchList.erase(allSuchList.begin() + i);		allSuchList.erase(allSuchList.begin() + i);
Line 161:		Line 161:
	//// 가장 시간이 낮은 경우를 제일 앞으로 둡니다. ////		//// 가장 시간이 낮은 경우를 제일 앞으로 둡니다. ////
	int minimumDelayPoint = 0;		int minimumDelayPoint = 0;
	int minimumDelay = allDelay[0];		int minimumDelay = allDelay[0];
	for (register int i = 1; i < (int)allSuchList.size(); ++i)		for (register int i = 1; i < (int)allSuchList.size(); ++i)
	{		{
	if (minimumDelay > allDelay[i])		if (minimumDelay > allDelay[i])
	{		{
	minimumDelay = allDelay[i];		minimumDelay = allDelay[i];
	minimumDelayPoint = i;		minimumDelayPoint = i;
	}		}
	}		}
	allDelay[minimumDelayPoint] = allDelay[0];		allDelay[minimumDelayPoint] = allDelay[0];
	vector<STown*> bufferSTown = allSuchList[minimumDelayPoint];		vector<STown*> bufferSTown = allSuchList[minimumDelayPoint];
	allDelay[0] = minimumDelay;		allDelay[0] = minimumDelay;
	allSuchList[0] = bufferSTown;		allSuchList[0] = bufferSTown;
	}while(0 != allSuchList.size());		}while(0 != allSuchList.size());
	}		}
Line 180:		Line 180:
	{		{
	for (register int i = 0; i < (int)g_myTowns.size(); ++i)		for (register int i = 0; i < (int)g_myTowns.size(); ++i)
	delete g_myTowns[i];		delete g_myTowns[i];
	}		}