shs9064   9달 전

기존에 버블정렬을 사용하여 제출 후 시간초과가 발생하여 이를 퀵정렬로 수정하여 재제출 하였음에도 여전히 시간초과가 뜨고 있습니다.

최대한 C언어로 베이직하게 해보고 싶어서 편의성을 위한 최소한의 라이브러리만 사용하고자 하였습니다.

전체 코드 플로우는 

이름 오름차순 정렬 -> 이름 입력 시 검색 수행 -> 답 출력입니다

예외 처리 등 누락된 것이 있다면 피드백 주시면 감사드리겠습니다!!

luckyandykang   9달 전

무작위화 등 적절하게 partition의 위치를 균등하게 만드는 기법이 없다면 quick sort의 시간 복잡도는 O(N^2)입니다.

최악의 경우에도 O(NlogN)에 정렬이 가능한 heap sort, merge sort 등으로 교체하시는 것을 추천합니다.

shs9064   9달 전

난수를 통해 최악의 경우를 개선하는 방법과 heap 모두 사용해 보았으나 문제가 해결되지 않네요 ㅜㅜ 

또 다른 문제가 있는 것 같습니다 ㅋㅋㅋ ㅜㅜ 댓글 감사드립니다!

tkvl94   9달 전

이거 몬스터 이름이

Aa

aA

일경우 어떻게 되는건가요?

compareName쪽에서 전부 소문자로 처리해서 continue 하고 
int 반환값이 없어서 문제되는게 아닌가 싶기도 하네요.

shs9064   8달 전

확인이 늦어졌습니다! 

continue되더라도 결국 다음 char가 없으면 1이 반환되도록 되어있습니다!


시간이 좀 된 지라 해당 케이스를 고려하고 작성했는지 기억이 안나서... 실행해보니 aA, Aa 각각 구분되는걸 확인하였습니다!


답변 주셔서 감사합니다!

shs9064   8달 전

답변 덕분에 compareName함수를 위주로 보다가 문제를 찾았습니다...

소문자 통일 과정에서 i번째 문자를 가져와야하는데 [0]으로 처리되고 있었습니다. 

도움주셔서 감사드립니다!!

tkvl94   8달 전

도움이 되셨다니 다행입니다.!
즐거운 하루되세요~

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