http://www.acmicpc.net/problem/2776

위 문제를 풀고 있는 대딩입니다

간단히 정리하면 최대 100만개의 정렬되지 않은 리스트에 key가 있는지 없는지 검사하는데, 그 key의 갯수도 최대 100만개입니다.
(숫자 범위는 int)

제가 이걸 며칠째 풀면서 생각나는 알고리즘은 다 써봤습니다 더 좋은 알고리즘이 있으면 알려주세요 


1. 퀵소트 + 선형 검색
->퀵소트 최악복잡도 O(n²) + 선형검색 O(n) 이라 너무 느림

2. 퀵소트 + 바이너리 검색

->퀵소트 최악복잡도 O(n²) + 바이너리 검색(O(log₂n)) 개선됐으나 여전히 시간초과..

3. 힙소트 + 바이너리 검색

-> 힙소트 최악복잡도 O(nlogn)+ 바이너리 검색(O(log₂n)) 여전히 시간초과..

4. g++ 환경이므로 tr1/unordered_map 사용

->시간초과

5. ext/hash_map 사용

->시간초과


멘붕올라캅니다 더 좋은 방법이 없나요? 제한시간이 1초.. 푼사람도 있긴하는데 저는 생각이 더이상 안나네요..