hack을 통해서 unordered_map을 저격하는 12번 테스트 케이스가 발생했다. 리해시 하면서 hash(key)의 결과가 동일한 bucket index로 충돌하도록 만든 케이스인 듯하다.
조치 방법
$O(logN)$으로 풀어도 충분하니, unordered_map이 아니라 map을 사용하면 된다. (375ms)
unordered_map 의 key를 의도적으로 충돌이 되도록 한 것이기 때문에, bucket size를 크게 늘려서 충돌이 적도록 만들자. unordered_map.reserve()를 통해서 처음부터 큰 사이즈로 할당하면 된다. TC별 input size에 맞게 적정하게 할당해주면 효율적이다. (218ms)
mp.clear();
mp.reserve(N * 3);
unordered_map을 쓸 땐 bucket key가 충돌하는 경우가 적도록reserve를 통해 미리 충분한 사이즈를 확보해주자.
킹갓 tourist님의 코드를 보니, map 자체도 필요가 없었다. T도 S와 동일하게 만드는 방법이 있었다.
S[i]가 만약 T[i]와 일치하지 않고 K - S[i]가 일치하면, 이는 S[i] == K - T[i]와 동일하다. 따라서, S를 min(S[i], K - S[i])로 정렬한다. T도 동일하게 정렬한다. S == T라면 YES다.