shfksekdrms2   2년 전

12%에서 계속 시간초과뜨네요...

아마 Arrays.sort() 써서 그런건가싶은데...

그럼 여기서 의도하는건

셀렉트 정렬, 삽입 정렬 등의 정렬 방식을 의도하는건가요...? 

도와주시면 감사하겠습니다... ㅜㅜ

djm03178   2년 전

선택 정렬, 삽입 정렬 등은 평균이 O(N^2)이라 더욱 좋지 않고요, 여기서 써야 하는 방법은 따로 있습니다. 참고로, https://www.acmicpc.net/step/9 에 힌트가 나옵니다.

shfksekdrms2   2년 전

djm03178 님 감사합니다. 알려주신 방법이 도움이 많이 됬습니다. 하지만 한가지 질문이 더 있습니다.

기수 정렬과 카운팅 정렬로 하는 방법이 있다고 써있던데 기수 정렬은 아직 해보지는 않았고
카운팅 정렬을 이용하여 정렬을 하였습니다. 그런데 여전히 시간 초과가 발생하는 군요... 이건 왜 그런건지 잘 모르겠습니다...
시간으로 보면 O(n) 시간 밖에 안드는데도 말이죠... 왜그런지 알 수 있을까요?

기수 정렬 방법은 시도후에 댓글 업데이트하겠습니다.

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