어떠한 n개의 unorderd list가 있고 하나의 key가 주어졌을 때
key가 그 리스트에 있는지 없는지 확인하는 프로그램을 짜는데 제가 쓴 방법은
1) 리스트를 힙소트로 정렬
2) 바이너리 서치로 key가 있는지 체크
n은 최대 100만까지라 시간복잡도에서 최악을 따져도 1000000log(1000000)+log_2(1000000) 정도라 1400만번 정도 돌아가는데
이게 왜 수행시간 1초내로 풀리지가 않는지 정말 미스테리 - -
있는지 없는지 확인하는데 왜 정렬을 해
그냥 뒤지면 O(n)에 찾을수있겠구만ㅋㅋ
하나의 list에 대해 찾아야될 key가 1개가 아니라 그렇슴다
선형검색하면 최악의 경우 O(sigma(n))까지 갈 수 있으므로...
key의 갯수가 최대 n개고 list를 초과한 범위의 key가 존재합니다 ㅠㅠ
해쉬테이블 만드는데 O(n), 찾는데 O(1)??
unordered_map을 써도 시간초과가 나네요..
http://www.acmicpc.net/problem/2776
이거풀고있었씁니다 ㅋㅋㅋ
언어 존나 많이 지원하네 ㅋㅋ 더블릿 ㅂㅂ2
http://pastebin.com/7pT8EB0w
이게 시간초과면 자바로 통과할 수 있는 방법은 없는거긔?
콘솔에 매번 출력하는거보다 StringBuilder 하나 만들어두고 한번에 출력하는게 훨씬 빠르긴 한데.. 그래도 시간초과이긴 마찬가지넹. 범위 작은 버전 문제는 통과하는데 쩝
http://www.acmicpc.net/status/?problem_id=1920&user_id=ahsexsex
Baekjoon Online Judge... 티버애니가 좋아하겠구만.
복잡도나 시간 나오는건 자바로 풀지 않는게 좋다.
대학생이 만든 사이트라 좋은 컴터쓰지도 않을테고 자바가 시간이랑 메모리에서 손해 많이 본다. 한국에서 자바로 acm하는 사람은 거의 없고.
근데 내가 생각해기에도 학부에서 배운 지식으로는 힙으로 낳고 꺼내는게 맞을거 같은데.. 정말 언어 문제 때문 아님?