Shell Sort/문보창

No older revisions available

소감 ¶

2005/02/28 Accepted(P.E.) 0:01.660 472
첨에 문제 파악을 잘못해서 중간에 코드를 뜯어고치느라 시간을 많이 허비했다. 귀찮아서 구상을 하지않고, 바로 코딩을 하다보니 발생한 사태였다. 수행시간이 다른사람에 비해 턱없이 길다. 나중에 보다 효율적인 접근방법을 찾아보겠다.

코드 ¶

~cpp 
// no10152 - Shell Sort
#include <iostream>
#include <cstring>
using namespace std;

const int MAX_NAME = 81;
const int MAX_TURTLE = 200;

void input_turtle(char turt[][MAX_NAME], const int & nTurt);
void move_turtle(const int * code, const int & nTurt, bool * isMove);
void incoding(const char oldTurt[][MAX_NAME], const char newTurt[][MAX_NAME], const int & nTurt, int * code);
void print_turtle(const char turt[][MAX_NAME], const int * code, const bool * isMove, const int & nTurt);
inline void show_turtle(const char turt[]) { cout << turt << endl; };

int main()
{
	char oldTurt[MAX_TURTLE][MAX_NAME], newTurt[MAX_TURTLE][MAX_NAME];
	int incode[MAX_TURTLE];
	int nCase, nTurt;
	cin >> nCase;
	int i;
	for (i=0; i<nCase; i++)
	{
		cin >> nTurt;
		cin.get();
		input_turtle(oldTurt, nTurt);
		input_turtle(newTurt, nTurt);
		incoding(oldTurt, newTurt, nTurt, incode);
		bool isMove[MAX_TURTLE] = {0,};
		move_turtle(incode, nTurt, isMove);
		print_turtle(newTurt, incode, isMove, nTurt);
		if (i != nCase-1)
			cout << endl;
	}
	return 0;
}

void input_turtle(char turt[][MAX_NAME], const int & nTurt)
{
	int i;
	for (i=0; i<nTurt; i++)
		cin.getline(turt[i], MAX_NAME, '\n');
}

void incoding(const char oldTurt[][MAX_NAME], const char newTurt[][MAX_NAME], const int & nTurt, int * code)
{
	int i, j;
	for (i=0; i<nTurt; i++)
	{
		for (j=0; j<nTurt; j++)
		{
			if (strcmp(newTurt[i], oldTurt[j]) == 0)
			{
				code[j] = i;
				break;
			}
		}
	}
}

void move_turtle(const int * code, const int & nTurt, bool * isMove)
{
	int i;
	int count = nTurt-1;
	if (code[count] != count)
		isMove[count] = true;
	else
		count--;
	for (i=nTurt-2; i>=0; i--)
	{
		if (code[i] != count)
			isMove[i] = true;
		else
			count--;
	}
}

void print_turtle(const char turt[][MAX_NAME], const int * code, const bool * isMove, const int & nTurt)
{
	int i, j;
	for (i=nTurt-1; i>=0; i--)
	{
		for (j=0; j<nTurt; j++)
		{
			if (isMove[j] && code[j] == i)
			{
				show_turtle(turt[code[j]]);
				break;
			}
		}
	}
}

ShellSort 문보창