시간복잡도가 같다고 해서 수행 시간도 같은 것은 아닙니다. 이 문제는 시간 제한이 상당히 빡센 편으로, 조금만 비효율적인 구현을 사용하더라도 얼마든지 시간 초과가 날 수 있습니다.
특히 map의 경우 균형 이진 트리를 사용하기 때문에 매우 매우 매우 매우 느립니다. 시간복잡도가 log일 뿐이지, 이분 탐색과는 비교가 되지 않습니다. unordered_map 역시 평균이 O(1)인 것이지, 실제로는 해시 충돌 등에 의해 굉장히 무거워질 수도 있는 자료구조입니다.
kyo20111 5년 전
이 문제는 map나 unordered_map 자료구조로 풀지 못하나요?
N2logN2 으로 이 문제를 푸는 일반적인 방법의 시간복잡도와 같지 않나요?