phd1150   2년 전

리스트와 sort()함수를 이용해서 원하는 위치(중간값)을 출력하도록 했습니다만 당연하게도 시간초과에 걸렸고

후에 질문과 블로그를 참고하여 heapq을 사용했는데도 시간초과에 걸리네요.

제가 응용을 잘못한 것 혹은 접근방법이 잘못된 것 같은데 도움 부탁드립니다.

whddnr0218   2년 전

Heap이라는 자료구조를 찾아보시면 아시겠지만 리스트를 완벽히 정렬해주지 않습니다.

보통 리스트를 사용하지만 베이스는 트리 기반의 자료구조라서 중간값을 꺼낸다고 해서 전체 리스트의 중간값을 가져올 수는 없습니다.

힙에서 사용할 수 있는 건 가장 최소(혹은 최대)값, 그리고 힙의 크기 정도입니다. 나머지는 별로 도움되는 값은 아니에요.

힌트를 하나 드리면 힙을 두개 써보세요. 파이썬에서 heapq를 이용해 최대 힙을 구현하는 법도 찾아보시면 좋을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.