글 읽기 - 푸는 과정에서(초보 C언어)

cksdnwh 6년 전 0

일단, 길이 정렬 할 때 퀵 소트를 이용하려 하는데요, 무한 루프가 도는 것 같습니다.

고민을 해봤지만 루프가 도는 이유를 찾지 못했습니다.

고수분들 알려주세요..

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

char words[20000][51];

void Sort_Words(int min, int max);
int main(void)
{
	int n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", words[i]);
	}
	Sort_Words(0, n - 1);

	for (i = 0; i < n;i++) {
		printf("%s\n", words[i]);
	}

}

void Sort_Words(int min, int max)
{
	if (min < max) {
		char temp[51];
		int m = min;
		int i = min + 1;
		int j = max;
		int len_m = strlen(words[m]);

		for (; ; ) {
			while (len_m > strlen(words[i]))
				i++;
			while (len_m < strlen(words[j]))
				j--;

			if (i >= j)
				break;

			strcpy(temp, words[i]);
			strcpy(words[i], words[j]);
			strcpy(words[j], temp);
		}
		strcpy(temp, words[j]);
		strcpy(words[j], words[m]);
		strcpy(words[m], temp);

		Sort_Words(min, j - 1);
		Sort_Words(j + 1, max);
	}
	return;
}

chogahui05 6년 전 1

퀵 정렬 정석으로 구현하기는 꽤 어려운데요..

저도 손코딩 하라고 그러면 memcpy 같은 메모리 복사 함수 2-3번 쓰면서 구현할 거 같네요.

하나 궁금한 건

단어의 최대 길이가 50이고요.

데이터 size가 최대 2만입니다.. 데이터 size가 n일 때 partition 하는 건..

O(50 * 2만 log (2만)) = 1500만..

그런데 저렇게 구현하시면 최악의 경우에는 O(50 * 2만 * 2만) = 200억

문자열의 길이는 최대 50이고, strcpy 역시 마찬가지입니다. 재수 없는 경우에는

swap 연산을 n/2번 하겠네요. swap은.. 최대 50*3번 가량의 연산을 하죠.. 대충 T(n) = 78n + 2*T(n/2)

앞에 붙는 78은 전처리를 하면 1로 줄일 수 있죠..

그냥

(1) 각 문자열의 길이를 미리 구해놓는 전처리를 하시고

(2) qsort 함수를 이용해서 구현하세요.

seico75 6년 전 1

m이 첫번째 인데, m가 가장 길 경우

while (len_m > strlen(words[i])) i++;

이 문장은 i 가 끝도 없이 증가할 것 같습니다.

피봇을 left, right 사이에 두는 것이 안전할 것 같습니다. (아니면 i < j 같은 비교문을 같이 넣던지..)

cksdnwh 6년 전 0

아 조건이 부족했었던 것 같습니다. 두 분 다 감사합니다~!

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

문제

문제

출처

ICPC

푸는 과정에서(초보 C언어)

cksdnwh 6년 전 0

chogahui05 6년 전 1

seico75 6년 전 1

cksdnwh 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말