20440번 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1
코드 넣어놨습니다.
run 함수 시작할 때 아래 코드를 실행시킵니다.
List keys = new ArrayList<>(m.keySet()); Collections.sort(keys);
m의 요소의 수는 최대 200만개이기 때문에, 이를 정렬하면 nlogn으로 계산하면 20억이 넘어갑니다.어떻게 시간초과가 나지 않는건가요?
n = 200만이고 정렬 알고리즘의 n log n이면 20억이 아니라 4천만 정도입니다
BOJ 에서 JVM 기반의 언어 (Java, Kotlin) 는 시간 제한이 x2+1초 로 되어있습니다. 이 문제의 경우는 3초가 주어집니다.
n = 2000000 일 때, log n 은 약 21 정도이며, n log n 은 약 42000000 정도 됩니다.
JVM 기반 언어라면 시간 보너스 받으면 얼마든지 충분히 시간 내에 풀 수 있고, 인터프리터 기반이 아닌 언어는 애당초 훨씬 넉넉하게 풀 수 있을 거라고 생각합니다.
댓글을 작성하려면 로그인해야 합니다.
toctoce00 1년 전
코드 넣어놨습니다.
run 함수 시작할 때 아래 코드를 실행시킵니다.
List keys = new ArrayList<>(m.keySet());
Collections.sort(keys);
m의 요소의 수는 최대 200만개이기 때문에, 이를 정렬하면 nlogn으로 계산하면 20억이 넘어갑니다.
어떻게 시간초과가 나지 않는건가요?