해쉬 충돌에 의해 시간이 시간 복잡도에 비해 오래 걸릴 수 있습니다.
해쉬맵은 두 자료를 평가하는 값을 이용하는데, 우연히 평가값이 같은 두 자료가 등장하면 O(N)의 시간을 소모하여 이를 해결합니다.
질문자님의 코드에서 해쉬맵의 최대 크기는 O(N^2)이므로 해쉬 충돌 몇 번으로도 시간 초과가 충분히 발생할 수 있습니다.
해결하기 위해서, 해쉬맵의 initializer로 new HashMap<>() 대신 new HashMap<>(N^2)를 사용하시는 것을 권장합니다.
(Java를 사용하지 않아 문법이 정확한지는 모르겠네요…)

cmy397264 1년 전
질문 게시판에 있는 여러 글을 통해 해당 문제는 해쉬 맵이 아닌 이분 탐색으로 풀어야 해결할 수 있다는 걸 알았습니다.
제가 궁금한 건 이분 탐색을 사용하기 위해선
배열이 정렬된 상태여야 하는데 A와 B를 합한 경우의 수를 담은 배열을 만들 때에도
아래 코드와 마찬가지로 n^2의 시간 복잡도를 가지지 않나요??