jumpingz   3달 전

STL 은 몰라서 못쓰겟고... 굳이 접근하자니 최대힙 최소힙을 이용해서 풀려고햇는데 자꾸 TLE 뜨네요...

힙을 쓰면 빠르긴하겟는데 최대 힙 및 최소 힙 사이에 동기화 시키는 과정이 오래걸려서 시간초과인거 같은데.. 어떻게 접근해야할까요???

아래는 일단 시간초과가 뜬 소스입니다...

flflds0811   3달 전

STL 기본 틀만 아시면 쉽게 사용하실 수 있습니다. STL사용하시는 걸 추천드려요.

굳이 STL을 사용하지 않고 문제를 푸시겠다면, 동기화까지 고려하여

삽입,삭제 O(logN) 탐색 O(1)에 구현하시면 충분히 시간 안에 들어오는 것으로 알고 있습니다.

힙을 두개를 만들어 포인터로 연결하시는 방식으로 구현하시거나,

하나의 heap이 min_heap,max_heap 모두를 갖추고 있는 MIN_MAX_HEAP이라는 자료구조를 공부하신 후,

구현해보시는 것이 좋을 것 같습니다. 

jumpingz   3달 전

min-max heap 자료구조 자세히 설명된 곳없을까요??? 삽입은 이해햇는데 삭제하는 방식이 구글링해서 찾은 자료로는 도무지 이해가 안가서리....

flflds0811   3달 전

아쉽지만 저는 학교 강의자료를 통해 공부한거라.. 따로 설명이 잘 되있는 곳은 모르겠네요..ㅜㅜ

jumpingz   3달 전

그러면 죄송하지만 요 코드좀 봐주실수잇나요?? min-max 공부하고 짯는데 계속 시간초과가 떠서 어디가 문제인지모르겟어요..

flflds0811   3달 전

쭉 보았을 때, 복잡도상 문제는 아닌것 같습니다.

몇 %까지 가시다 시간초과가 나시는지..?

최적화 문제일 것같습니다. 

분기문이 많은 편이라 제한시간 안에 들어오지 못하는 것 아닐까요??

ㅜㅜ

jumpingz   3달 전

그냥 시작부터 시간초과나더라구요 ㅋㅋㅋ 부끄럽지만 1%.. ㅠ 아 이틀넘게 자료 찾으면서 공부햇는데.. 허탈하네요.. 분기문을 좀 어떻게 줄여보면 되려는지요...?

flflds0811   3달 전

글쎄요.... 확신은 못 하겠네요;; 저는 포인터로 연결하는 방식으로 짜둔걸 제출했을 때

3100으로 통과한거라 시간복잡도가 만족해도 앞의 상수가 커지면 시간초과가 나는 것 같은데;;

어느정도로 맞춰야하는지는 저도 잘 모르겠네요...ㅜ

jumpingz   3달 전

아... 동일한 값이 여러개 입력되면 삭제 시 무한루프가 발생하는걸 찾앗습니다... 일단 요걸 해결해봐야할 듯하네요 ㅎㅎㅎ

감사합니다.

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