자료구조중에 priority_deque같은건 없음?

[익명(112.152)]

지금 필요한 기능이

begin end pop_begin pop_end insert 이 기능인데

이걸 set로 하는거 begin,end 찾는게 logn이라 몬가 존나 손해보는 느낌이라서 쯔증남

잘만하면 구현할 수 있을거같은데 STL에 없는거 보니 효율이 별로인가..

[ㅇㅈ(112.169)]

C++ STL 에 priority queue 있어요

[익명(112.152)]

deque

[ㅇㅈ(112.169)]

STL deque 도 push_front, push_back 제공할거에요

[익명(112.152)]

priority queue - value에 따라 정렬된 begin 하나만 pop가능 deque - 정렬되지않고 입력순서에 따라 넣은 데이터중 begin, end 접근 빠름 내가 원하는건 정렬된 데이터에 begin end 접근이 빠른거야

[익명(112.152)]

백준 7662와 비슷하다고 보면됨 하지만 백준은 한번 출력하면 끝이라 야매로 최적화가 가능해서 별루

[ㅇㅈ(112.169)]

이론적으로 정렬상태 유지하면서 O(1) 수준으로 조회 삽입 삭제가 되는건 본적이 없네요 .. 차라리 자료구조 2개 쓰셔서 Hash + sorted Array 생성해서 index 로 참조하고, 삽입 삭제는 해시로 하시는게 어떨까 싶습니다.

[익명(112.152)]

확인 고민해줘서 고마어!

[익명(122.32)]

https://cplusplus.com/reference/deque/deque/
이거?

[익명(112.152)]

모야 제 priority_deque 돌려줘요..

[nvm(milizz)]

그냥 begin end를 외부에서 계산해놓으면 되지 않을까 싶네. insert할때마다 begin end보다 크거나 작으면 업데이트 하고 문제는 pop인데 pop할때 begin end랑 같으면 pop한 직후에 begin end새로 구하면 될듯? insert랑 pop은 o(logn)이지만 lookup은 o(1) 가능하지 않나

[익명(112.152)]

사실 외부에서 pop 기록하는게 맞는말이긴해 혹시 set이랑 priority_queue 각각의 begin값 추가 제거가 속도차이가 별로 없을까? 별로없으면 지금 고민이 의미없는게 맞긴 해

[익명(112.152)]

지금 고민이 만약 priority_queue begin 추가제거가 확실히 빠르다면 만약 begin end접근만 필요하다면 set을 쓰는것보다 priority_queue 양방향으로 섞어보면서 개선여지가 있는건가 고민하는거라

[nvm(milizz)]

priority queue를 min하나 max하나 두개 만든다 이건가? 이렇게 하면 pop이 불가능 할 거 같은데

[익명(112.152)]

그래도 평소에 버스탈때 고민하면 재밌으니까 ㅋㅋㅋ 그래도 역시 set보단 priority_queue가 추가 제거 접근이 더 빠르겠지?

[nvm(milizz)]