정렬이 시간을 많이 잡아먹기 때문입니다.

scanner도 내부적으로 느리게 동작한다고 알고있습니다.

자바는 기본적으로 5초의 시간보너스를 받는데,

그래도 시간초과라는것은 알고리즘을 바꿔야할 필요가 있어보입니다.

그 for문 도중에 있는 sort 가 전체적으로 보면 n^2 log n 이므로 실제 시간 복잡도는 n^2 이 아니라 n^3 log n 이네여..

이러면 1500 이라도 약 33750000000 번 정도의 루프를 돌게 되구요 실제로는 더 작게 돌겠지만 거의 그정도라고 생각합니다.

밑에는 시간복잡도 분석입니다.

n log n + 2n log 2n + 3n log 3n + .... + n^2 log n^2

 = (log 1 + 2 * log 2 + 3 * log 3 + ... n * log n) * n + (1 + 2 + 3 +... + n) * n log n

= O(n^3 log n)

알고리즘을 조금 바꿔보세요!

아니면 정렬을 밖으로 빼셔도 시간복잡도가 뭉텅이로 줄어듭니당

모든 원소를 다 담는게 아니라 N * 2 크기의 원소만을 담아서 정렬하므로

시간 복잡도는 N^2logN이 맞는것 같습니다.

아, 그렇네요!

잘못봤네요 ㅠㅠ