글 읽기 - [C] 제 미천한 지식으로는 왜 틀렸는지 알 수가 없습니다.

emperor 4년 전 0

선생님들 미천한 중생을 구원해 주십사 글을 올립니다.

코드가 좀 길지만, 한 번 올려봅니다.

1개, 2만개, 20만개, 중복으로만 2만개, 50짜리 문자열 10만개 등등 온갖 극한의 사례로

앞보다 뒤의 문자열 길이가 짧거나,

길이가 같다면 사전순이 아닐 때, error 의 수를 ++ 하는 방식으로 디버깅을 하였습니다만 오류가 없었습니다.

더 이상 제 힘으로는 찾을 수 없을 것 같습니다.

C언어 교수님들 어디가 잘못되었는지 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <string.h>

char input[20000][51];
int check[20000] = { 0 };


void Eqsort_len(char ar[][51], int start, int end)
{
	int i, j;
	int std, std_25, std_50, std_75;
	int End_of_array = end;
	char temp[51];


	for (i = 0; i <= End_of_array;)
	{
		if (end - start <= 1)
		{
			if (strlen(ar[start]) > strlen(ar[end]))
			{
				strcpy(temp, ar[start]);
				strcpy(ar[start], ar[end]);
				strcpy(ar[end], temp);
			}

			start = end + 1;
		}
		else
		{
			std_25 = strlen(ar[start + (end - start) / 4]);
			std_50 = strlen(ar[start + (end - start) / 2]);
			std_75 = strlen(ar[start + 3 * (end - start) / 4]);

			if ((std_25 > std_50&& std_25 < std_75) || (std_25 < std_50 && std_25 > std_75))
				std = std_25;
			else if ((std_75 > std_25&& std_75 < std_50) || (std_75 < std_25 && std_75 > std_50))
				std = std_75;
			else
				std = std_50;

			for (i = start, j = end; i <= j;)
			{
				while (strlen(ar[i]) < std)
					i++;

				while (strlen(ar[j]) > std)
					j--;

				if (i <= j)
				{
					if (strlen(ar[i]) != strlen(ar[j]))
					{
						strcpy(temp, ar[i]);
						strcpy(ar[i], ar[j]);
						strcpy(ar[j], temp);
					}

					i++;
					j--;
				}
			}

			if (start < j)
			{
				check[start] = 1;
				check[j] = 2;
			}
			else
			{
				start++;
				check[start] = 1;
			}

			if (i < end)
			{
				check[i] = 1;
				check[end] = 2;
			}
			else
			{
				check[end - 1] = 2;
				check[end] = 0;
			}
		}

		for (i = start; i < End_of_array; i++)
		{
			if (check[i] == 1)
			{
				start = i;
				break;
			}
		}
		for (i = start + 1; i <= End_of_array; i++)
		{
			if (check[i] == 2)
			{
				end = i;
				break;
			}
		}
	}
}

void Eqsort_dic(char ar[][51], int start, int end)
{
	int i, j;
	int End_of_array = end;
	char temp[51];
	char std[51], std_25[51], std_50[51], std_75[51];


	for (i = 0; i <= End_of_array;)
	{
		if (end - start <= 1)
		{
			if (strcmp(ar[start], ar[end]) > 0)
			{
				strcpy(temp, ar[start]);
				strcpy(ar[start], ar[end]);
				strcpy(ar[end], temp);
			}

			start = end + 1;
		}
		else
		{
			strcpy(std_25, ar[start + (end - start) / 4]);
			strcpy(std_50, ar[start + (end - start) / 2]);
			strcpy(std_75, ar[start + 3 * (end - start) / 4]);

			if ((strcmp(std_25, std_50) > 0 && strcmp(std_25, std_75) < 0) || (strcmp(std_25, std_50) < 0 && strcmp(std_25, std_75) > 0))
				strcpy(std, std_25);
			else if ((strcmp(std_75, std_25) > 0 && strcmp(std_75, std_50) < 0) || (strcmp(std_75, std_25) < 0 && strcmp(std_75, std_50) > 0))
				strcpy(std, std_75);
			else
				strcpy(std, std_50);

			for (i = start, j = end; i <= j;)
			{
				while (strcmp(ar[i], std) < 0)
					i++;

				while (strcmp(ar[j], std) > 0)
					j--;

				if (i <= j)
				{
					if (strcmp(ar[i], ar[j]) != 0)
					{
						strcpy(temp, ar[i]);
						strcpy(ar[i], ar[j]);
						strcpy(ar[j], temp);
					}

					i++;
					j--;
				}
			}

			if (start < j)
			{
				check[start] = 1;
				check[j] = 2;
			}
			else
			{
				start++;
				check[start] = 1;
			}

			if (i < end)
			{
				check[i] = 1;
				check[end] = 2;
			}
			else
			{
				check[end - 1] = 2;
				check[end] = 0;
			}
		}

		for (i = start; i < End_of_array; i++)
		{
			if (check[i] == 1)
			{
				start = i;
				break;
			}
		}
		for (i = start + 1; i <= End_of_array; i++)
		{
			if (check[i] == 2)
			{
				end = i;
				break;
			}
		}
	}
}


int main(void)
{
	int i;
	int n, start;


	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%s", input[i]);
	}

	Eqsort_len(input, 0, n - 1);

	for (i = 0; i < n; i++)
		check[i] = 0;

	start = 0;

	for (i = 1; i <= n; i++)
	{
		if (i == n)
		{
			Eqsort_dic(input, start, i - 1);

			break;
		}

		if (strlen(input[i - 1]) != strlen(input[i]))
		{
			Eqsort_dic(input, start, i - 1);

			start = i;
		}
	}

	printf("%s\n", input[0]);

	for (i = 1; i < n; i++)
	{
		if (strcmp(input[i - 1], input[i]) != 0)
			printf("%s\n", input[i]);
	}


	return 0;
}

nahwasa 4년 전 1

?!..

랜덤 데이터 만들어서 제꺼랑 비교해보고 있었는데..

잘되는것같길래

걍 그대로 제출해보니 통과 됩니..다?

solarmagic 4년 전 2

https://www.acmicpc.net/board/view/32737

반드시 틀린 코드 그대로를 한 자도 다름없이 올립시다. 로컬에서 테스트한 코드가 아니라, ★☆★☆★ 제출했던 코드 그대로 ★☆★☆★ 를 말하는 것입니다. 제출한 코드는 '내 소스' 탭에서 언어 이름을 클릭하면 볼 수 있으니 반드시 그 코드 그대로를 복사합시다. 한 글자라도 다른 코드를 올리면 제출 시 받았던 채점 결과와 전혀 다른 결과를 받을 수도 있고, 엉뚱한 곳에서 다른 오류가 생길 수도 있습니다. 심지어 틀린 부분을 고쳐서 맞는 코드를 만들어놓고도 제출을 안 해보고 질문을 올리는 경우도 심심찮게 보입니다. 꼭 마지막에 제출했던 코드 그대로를 올려주세요. 또한 코드는 반드시 전체를 올려야 다른 사람들도 복사해서 직접 테스트 해볼 수 있을 뿐 아니라, 내가 맞았다고 확신한 부분이 문제의 원인일 수도 있기 때문에 아무리 상관이 없어 보여도 꼭 전체를 올려야 합니다.

주석 없는 긴 코드라 꽤 오랜시간 동안 로컬에서 디버깅 하고 있었는데
위의 말을 듣고 제출해보니 정말 잘 되는군요...
답변자의 수고를 생각해서라도 이런일은 없도록 하셨으면 합니다

emperor 4년 전 1

아니 선생님들 정말 죄송합니다.

가독성을 위해, 영향을 1도 안 줄 것 같은 최적화 코드를 지웠는데

그게 문제였나 보네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C] 제 미천한 지식으로는 왜 틀렸는지 알 수가 없습니다.

emperor 4년 전 0

nahwasa 4년 전 1

solarmagic 4년 전 2

emperor 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말