Shell Sort/문보창

소감 ¶

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

[edit]

코드 ¶

~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 문보창