small to large를 쓰려면 작은 집합을 A, 큰 집합을 B라 할 때 A와 B를 합칠 때 O(|A|)만큼의 연산만 이루어져야 합니다. 그래야 마지막에 N개로 합쳐질 때 O(N log N)번만 이동함이 보장됩니다.
지금은 두 vector를 합칠 때 아무리 못해도 O(|A|+|B|)가 들어서 총 O(N^2)입니다. 위의 코드처럼 합칠 때마다 sort() 해버리면 더욱 느리고요.
만약 child node에 있는 정렬된 벡터 K개를 parent로 한꺼번에 빠르게 합칠 방법이 있으면 가능할수도 있습니다.
p_ce1052 3년 전
small to large 테크닉으로도 풀릴거같아서 짜봤는데 40퍼쯤에서 시간초과가 나네요 small to large로 못푸는 문제인가요? 그냥 머지소트트리 + euler walk 를 써야하나요?