jks961616   5달 전

이게 제 코드입니다. 제목에서 아시겠지만 버블소트를 사용하였습니다.


그런데 버블소트를 사용하니 시간초과가 나오더군요.


버블 소트를 이용하였을때 시간초과에 걸리지 않는 방법이 있나요?


버블소트는 시간복잡도가 N2이라 힘들것같아요ㅠㅠ

nisroeld99   5달 전

nlogn 정렬 공부해보세요 

yclock   5달 전

이 문제는 다른 정렬 문제와 다르게 특수한 조건이 있기 때문에,

O(N)만에 풀 수 있습니다.


버블소트 등과 같은 정렬 알고리즘은 O(N2)이기 때문에, N의 최대값이 106인 이 문제를 시간 안에 풀기는 어렵습니다.

퀵소트나 Merge Sort같은 O(N log N) 알고리즘을 공부해보시기 바랍니다.

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