글 읽기 - C언어로 풀었는데 반례좀 부탁드리겠습니다.

ssssksss 3년 전 0

1번 단어가 50자 일때

aaaaabbbbbcccccdddddeeeeeaaaaabbbbbcccccdddddeeeee

2번 마지막 단어의 길이가 가장 짧을때

abc

cde

bcd

asd

3번 모든 단어의 길이가 같을 경우

이런식으로 반례를 해보아도 틀린것은 없는데 잘 모르겠습니다. 문제점이나 반례를 찾아주시면 감사하겠습니다.

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

int N;
char raw_data[20001][51];
void quick_sort(int first, int end);
int main()
{
	scanf("%d", &N); // 1<=N<=20000

	for (int i = 0; i < N; i++)
	{
		scanf("%s", raw_data[i]);
	}

	quick_sort(0, N - 1);

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

void quick_sort(int first, int end) //퀵정렬 조건 순서 1. 길이, 2. 인덱스
{
	int count = first;
	if (first < end && end > 0)
	{
			for (int i = first; i <= end; i++)
			{
				if (strlen(raw_data[i]) < strlen(raw_data[end])) //문자열 길이 비교(왼쪽이 짧을때)
				{
					char temp[51];
					strcpy(temp, raw_data[i]);
					strcpy(raw_data[i], raw_data[count]);
					strcpy(raw_data[count], temp);
					count++;
				}
				else if (strlen(raw_data[i]) == strlen(raw_data[end]))
				{
					if (strcmp(raw_data[i], raw_data[end]) == -1) //문자열 순서
					{
						//왼쪽이 더 빠를경우
						char temp[51];
						strcpy(temp, raw_data[i]);
						strcpy(raw_data[i], raw_data[count]);
						strcpy(raw_data[count], temp);
						count++;
					}
				}
				if (i == end)
				{
					if (strlen(raw_data[count]) > strlen(raw_data[end]))
					{
						char temp[51];
						strcpy(temp, raw_data[i]);
						strcpy(raw_data[i], raw_data[count]);
						strcpy(raw_data[count], temp);
					}
					else if (strcmp(raw_data[end], raw_data[count]) == -1)
					{
						char temp[51];
						strcpy(temp, raw_data[i]);
						strcpy(raw_data[i], raw_data[count]);
						strcpy(raw_data[count], temp);
					}
				}
			}
		quick_sort(first, count-1);
		quick_sort(count +1, end);
	}
}

seico75 3년 전 1

strcmp 는 0이냐 음수, 양수이지, 0, 1, -1 로 값을 주도록 되어 있지 않습니다.

https://en.cppreference.com/w/cpp/string/byte/strcmp

Return value

Negative value if lhs appears before rhs in lexicographical order.

Zero if lhs and rhs compare equal.

Positive value if lhs appears after rhs in lexicographical order.

Example

ssssksss 3년 전 0

시간초과가 발생은 하였지만 일단 전에보다는 좋아졌습니다. 감사합니다

seico75 3년 전 0

strcmp, strlen, strcpy 모두 문자열 길이에 비례하는 연산시간이 들어서 quick 소트 내에서 시간을 많이 소모할 것 같습니다.

strcmp 는 어쩔 수 없다고 해도 strlen 문자열 길이는 미리 계산해놓고 사용하고,

strcpy 는 없애서.. 문자열 카피가 아니라 문자열의 index 를 옮기는 식으로 수정하면 어떨까 합니다.

char str[문자열 최대수][문자열 최대 길이 + 1];

int index[문자열 최대수];

처음에 index 의 값은 모두 자기 위치와 동일하게 하고 index[i] = i;

소트할때 str[index[i]] 와 str[index[j]] 를 비교하면서 index[i] 와 index[j] 의 값을 바꾸는 식으로요..

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

문제

문제

출처

ICPC

C언어로 풀었는데 반례좀 부탁드리겠습니다.

ssssksss 3년 전 0

seico75 3년 전 1

Return value

Example

ssssksss 3년 전 0

seico75 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말