CLASS 3 ESSENTIAL
이중 우선순위 큐를 구현하는 문제입니다. 문제 이름을 보니 우선순위 큐를 가지고 뭔가 풀어야 될 것 같이 생겼습니다. 처음에는 최대 힙과 최소 힙을 만들어놓고 원소를 삽입할 때에는 둘 다 삽입하고, 최대 또는 최소 원소를 제거할 때는 한 쪽만 제거해놓고 최소 힙의 루트가 최대 힙의 루트보다 크면 두 힙을 모두 비우는 방식을 떠올렸습니다. 그런데 긴 시간(무려 하룻밤)을 생각해보니 원소가 중복일 때에는 원하는 결과가 나오지 않는 것이었습니다. 그래서 질문을 돌아다니다가 삭제한 원소를 저장하는 트리, 굳이 따지면 삭제 버퍼를 만드는 내용이 있었습니다. 그래서 이것을 가지고 만들어보았습니다.
먼저 최대 힙과 최소 힙을 준비하고, 삭제한 원소에 대한 힙을 각 힙에 대해 준비합니다. 삽입 명령(I)에 대해서는 최대 힙과 최소 힙에 모두 값을 대입합니다. 최대값 삭제 명령(D 1)에 대해서는 최대 힙에서 삭제 연산을 수행하고 최소 힙에 대한 삭제 힙에 원소를 대입합니다. 최소값 삭제 명령(D -1)에 대해서도 마찬가지로 최소 힙에서 삭제하고 최대 힙의 삭제 힙에 원소를 대입합니다. 삭제 명령이 끝난 후에는 각 힙에 대해 삭제 힙과 루트를 비교하여 같으면 원래 힙과 삭제 힙의 루트를 제거합니다. 이렇게 하면 이중 우선순위 큐에는 존재하지 않지만 최대 힙 또는 최소 힙에 존재하는 원소가 루트에서 발견되는 즉시 삭제할 수 있습니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-12-22 21:55:45 |