djm03178   5년 전

정렬을 위해 삽입 정렬을 사용한 코드가 통과됩니다. https://www.acmicpc.net/source...

stack에서 역순 정렬 데이터로 돌려본 결과 3092ms가 뜨는 것으로 보아, 삽입 정렬의 기댓값상 시간이 반 정도 걸리는 랜덤 케이스밖에 없는 것 같습니다.

이전 질문에서 퀵소트가 통과된다고 하는데 만일을 위해(?) 모두 같은 원소인 것과 정렬된 데이터도 만들었습니다.

data.zip

그리고 시간 제한을 줄이는 것도 제안해 봅니다. 올바른 시간 복잡도의 코드라면 C++ 기준으로 0.3초 이상이 걸릴 이유가 없어보이고, endl은 어차피 지금도 통과가 안 됩니다. 2초는 가벼운 O(N^2)을 지금이나 근미래에 통과시킬 가능성이 높고 언어 보너스로도 뚫릴 여지가 있어 보입니다.

startlink   5년 전

재채점했습니다.

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