배움과 성장/알고리즘·문제풀이
백준 7662 이중 우선순위 큐 Java: TreeMap으로 중복값까지 관리하기
백준 7662번 원문에는 한 달 만에 다시 풀었고, 문제를 붙잡은 시간은 사실상 하루 꼬박이었다고 적혀 있다. 가장 오래 막힌 이유도 분명했다. 문제 이름이 ‘이중 우선순위 큐’라서 최소 힙과 최대 힙만으로 끝내려 했지만, 두 자료구조에서 삭제된 원소를 동기화해야 했다.백준 7662번 이중 우선순위 큐두 힙과 지연 삭제(lazy deletion)를 조합해도 풀 수 있다. 다만 Java에서는 정렬된 key와 각 값의 개수를 함께 관리하는 TreeMap 하나가 더 단순하다.필요한 것은 정렬된 다중 집합이다문제의 연산은 세 가지다.I value: value 한 개 삽입D -1: 현재 최솟값 한 개 삭제D 1: 현재 최댓값 한 개 삭제같은 값이 여러 번 들어올 수 있으므로 단순한 TreeSet은 맞지 않는다. ..