최대 크기의 데이터가 주어졌을 때, 생성되는 Edge 객체의 개수는 1000000개 입니다
제출번호 100087548 의 경우 Edge 객체 하나의 크기는 12 byte, 제출번호 100087594 의 경우 8 byte 입니다.
반면, 등장할 수 있는 길의 유지비의 "종류"는 1000 종류이기 때문에,
제출번호 100087594 는 제출번호 100087594 보다 ArrayList 객체 999개 와 HashMap 객체 1개를 더 생성합니다.
.
생성되는 Edge 객체의 개수가 워낙 많다 보니까
Edge 객체의 메모리 감소가 ArrayList + HashMap 객체 추가 생성에 의한 메모리 증가보다 훨씬 큽니다.
.
ps) 사람마다 관점이 다를 수 있지만
제출번호 100087594 에서 사용한 기법을 "정렬을 생략했다" 라기 보다는 "카운팅 정렬 (Counting Sort)을 사용했다" 라고 봅니다.
이 문제로 경험하신 것 처럼 입력 데이터의 개수에 비해 정렬하려는 키의 종류가 좁을 때 유리한 정렬 방식입니다.

injaesong 1년 전
자바로 일반적인 크루스칼 알고리즘으로 풀었습니다.
다만 2가지 정도 추가해서 시간복잡도를 더 개선시켜봤어요.
1. Union을 할 때마다 카운트해서 카운트가 n - 2면 break
2. 카운팅 배열을 통해 정렬 생략
2번은 사실 배열보단 해시맵을 사용했습니다.
시간복잡도가 개선은 됐습니다.
하지만 카운팅 배열을 사용하면 메모리를 더 많이 잡아먹을거라고 생각했는데, 오히려 메모리도 개선됐더라고요.
왜 그렇게 되는건지 잘 생각을 해봐도 감이 잘 안 잡혀서 질문 남겨봅니다.
도와주시면 감사하겠습니다.
첫번째가 카운팅 배열을 사용했을 때고, 두번째가 정렬 했을 때입니다.