toctoce00   1년 전

코드 넣어놨습니다. 

run 함수 시작할 때 아래 코드를 실행시킵니다.

List keys = new ArrayList<>(m.keySet());
Collections.sort(keys);

m의 요소의 수는 최대 200만개이기 때문에, 이를 정렬하면 nlogn으로 계산하면 20억이 넘어갑니다.
어떻게 시간초과가 나지 않는건가요?

radahn   1년 전

n = 200만이고 정렬 알고리즘의 n log n이면 20억이 아니라 4천만 정도입니다

bupjae   1년 전

BOJ 에서 JVM 기반의 언어 (Java, Kotlin) 는 시간 제한이 x2+1초 로 되어있습니다. 이 문제의 경우는 3초가 주어집니다.

n = 2000000 일 때, log n 은 약 21 정도이며, n log n 은 약 42000000 정도 됩니다.

JVM 기반 언어라면 시간 보너스 받으면 얼마든지 충분히 시간 내에 풀 수 있고, 인터프리터 기반이 아닌 언어는 애당초 훨씬 넉넉하게 풀 수 있을 거라고 생각합니다.

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