wlsth1004100   5년 전

소스를 단순 요약을 하자면

  1. n을 입력을 받으면 2차 문자배열을 동적할당합니다 char list[n][51];
  2. 합병정렬을 이용하여 정렬합니다. 문자열 길이를 비교하여 적은쪽을 temp배열에 먼저 넣어놓고

     만약 문자열 길이같을시엔 check함수를 통해 누가더 먼저넣는지에 대해 알아낸후 temp배열에 넣는다.

3. 다 정렬되면 display함수를 통해 출력을하는데 check변수를 통해  중복출력을 대비한다.

이와 같이 코딩하였으며 예제 잘나오고 질문게시판에있는 데이터도 잘나오는데 틀린부분이나 반례 찾아주시면 감사하겠습니다! ㅠㅠ

djm03178   5년 전

check 함수가 잘못되었습니다.

2

aa

ab

wlsth1004100   5년 전

지적해주신 check 함수 if (left[i] == right[i]) return check(left, right, i + 1); 

바꿔서 문제는 잘해결된듯하나 시간초과가 뜨네요 ㅠㅠ

제 나름 시간복잡도 줄일려고 병합정렬을 사용했는데 더 줄일방법이 있을까요??

djm03178   5년 전

comparison 함수를 재귀로 구현하셨는데, 매 글자마다 strlen을 호출할 필요가 없습니다. 길이 비교는 처음에 한 번만 하면 되니까요. strlen은 문자열 전체를 다 돌아야 그 길이를 알 수 있기 때문에 O(길이)의 시간이 걸리고, 그걸 전체 문자에 대해서 다 수행하고 있으니 O(길이^2)의 시간이 걸립니다.

wlsth1004100   5년 전

생각해보니 strcmp함수가 있어서 바꿧더니 시간초과가 안뜨네요 ㅠㅠ 매번 답변달아주셔서 감사합니다!

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