cksdnwh   4년 전

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

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

고수분들 알려주세요..

chogahui05   4년 전

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

저도 손코딩 하라고 그러면 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   4년 전

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

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

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

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




cksdnwh   4년 전

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

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