kkw564   11달 전

퀵정렬로는 해결이 되질 않네요..


퀵마저 시간초과입니다.ㅠㅠ

도와주세요

kesakiyo   11달 전

한 배열의 길이가 N이고 다른 배열의 길이가 M일때

퀵소트의 평균 시간복잡도는 (N+M)log(N+M) 이죠.

근데 이게 TL이 났단거는 더 빠른 방법이 필요하단거겠죠?

여기서 주어지는 두개의 배열은 정렬된 상태라는 점을 이용해야 됩니다.

merge sort가 어떻게 동작하는지 생각을 해 보시면 해답을 찾을 수 있을거에요.

onjo0127   11달 전

두 배열이 이미 정렬되어 있다는 점을 이용해보세요

이걸 이용하면 O(n+m)에 문제를 풀 수 있습니다

(<algorithm>에 정의되어있는 sort를 사용하면 시간초과가 나지 않더군요...? 같은 퀵소트인데 왜 그럴까요?)

kkw564   11달 전

책에 있는 sort를 이용했는데 음.... 퀵소트가 같은데 왜그런거죠.. ㅠㅠ;;


merge sort도 다시 연구해 봐야겠네요..

shashack   11달 전

퀵소트 같은 경우 이미 정렬이 즉, 처음에 A B를  지금 arr에 그대로 담으셨는데

이미 이것이 정렬되어 있는 상태라면 복잡도는 n^2입니당 

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