rkdgh248   4달 전

같은 문제를 삽입 정렬로 풀었을 때는 시간초과가 나지 않았습니다. 

하지만 삽입 정렬보다 더 빠른 퀵 정렬로 해당 문제를 푸니 시간초과가 나오네요ㅜ

혹시 제가 실수한 부분을 찾으셨다면 답변 부탁드리겠습니다.

djm03178   4달 전

퀵 정렬은 최악의 경우 O(n^2)이므로 삽입 정렬보다 빠르지 않습니다.

그런데 정말 삽입 정렬이 통과되었나요? 그것도 통과시키지 않는 것이 의도라고 생각됩니다. 데이터의 추가나 시간 제한의 조정이 필요할지도 모르겠습니다.

djm03178   4달 전

이 문제에서 정답을 받으신 적이 없는데, https://www.acmicpc.net/proble... 를 말씀하신 거라면 둘은 제한이 다르므로 다른 문제입니다.

rkdgh248   4달 전

앗 그렇네요. 

병합 정렬이나 힙 정렬을 사용해보겠습니다.

감사합니다!

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