key262yek   3년 전

현재 rust 2021의 컴파일 버젼은 1.65 (2022-11-02) 로 확인됩니다. 

마지막 업데이트가 채 세 달이 되지 않았으니 좀 이른 요청이란 생각은 들지만 혹시 몰라 요청 올려봅니다.

주요 사유는 BTreeSet의 pop_first 구현이 nightly 에서 stable로 옮겨온 것이 1.66이기 때문인데요. 

기존 BTreeSet stable 구현체는 set의 역할만 해서 union / intersection 등의 집합 연산에만 사용될 수 있었습니다. 

하지만 이왕 Binary tree 구조를 가지고 있는 김에, 최솟값 / 최댓값을 사용하는 priority queue 기능에 대한 수요가 있어왔고, 1.66에 들어 stable로 옮겨왔습니다. 

업데이트 이전에 priority queue를 구현하기 위해서는 VecDeque 구현체에 binary search 기능을 추가해 사용할 수밖에 없었지만

지금은 보다 쉽게 구현할 수 있게 된 것이죠. 

1753 문제는 priority queue 를 사용하여 Dijkstra 알고리즘을 구현해야 시간 제한 안에 풀이가 가능한 것으로 압니다. 

standard library를 사용해 문제 풀이가 가능하도록 업데이트 요청 드립니다. 

kiwiyou   3년 전

BinaryHeap을 사용하시면 됩니다.

key262yek   3년 전

BinaryHeap을 몰랐네요. 감사합니다. 

kiwiyou   3년 전

참고로, iter()로 최대 및 최소를 가져오고 remove하는 식으로 pop을 구현할 수 있습니다.

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