O( n^2 * log n ) 의 풀이로 문제를 풀었습니다만, 시간 초과의 벽에 번번히 막히고 있습니다. 

그 과정에서 map을 사욯했는데, map의 overhead가 워낙 커서 시간 초과가 뜨는지, 아니면 애초에 이 시간 복잡도로 풀 수 없는 문제인지 잘 모르겠습니다. 

n=1000이라 충분했다고 생각했지만 생각해보니 테스트 케이스가 여러개라서... 그런가 싶기도 하고요.

혹시 이 문제를 O(n^2) 으로 풀 수 있는 방법이 존재하는 건가요? 

혹시 이 문제를 O(n^2)으로 푸신 분이 있다면, O(n^2)으로 풀 수 있다고 알려주시면 감사하겠습니다. 

만약 이 질문이 문제시 되어 삭제해야 한다면 삭제하겠습니다.