쉽게 쉽게

이 글은 TreeMap 실전 활용 편에 이어지는 글입니다.📌 핵심 요약정렬이 아니라 "다음에 처리할 하나"를 뽑는 도구다 — 전체를 정렬하지 않고도 최솟값만 O(1)에 확인할 수 있다기본은 최소 힙 — 최대 힙이 필요하면 Comparator.reverseOrder()를 넘긴다상위 N개는 반대로 담는다 — 큰 값을 구하는데 최소 힙을 쓴다. 버릴 것을 맨 앞에 두기 위해서다순회 결과는 정렬 순서가 아니다 — 정렬된 순서를 보려면 반드시 poll로 꺼내야 한다 목차1 언제 PriorityQueue를 쓰는가작업 목록에서 우선순위가 가장 높은 것부터 처리해야 한다고 해봅시다. 그런데 처리하는 도중에도 새 작업이 계속 들어옵니다. Java — List로 처리하면while (!tasks.isEmpty()) { ..

📌 핵심 요약힙 하나로는 안 된다 — PriorityQueue는 루트 한쪽 끝만 정렬을 보장한다. 최소 힙에서 최댓값의 위치는 알 수 없다.풀이 1: TreeMap — 값을 키, 개수를 밸류로 저장한다. firstKey와 lastKey로 양쪽 끝을 각각 O(log n)에 얻는다.풀이 2: 두 개의 힙 — 최소 힙과 최대 힙에 같은 값을 넣고, 한쪽에서 꺼낸 값을 다른 쪽에서 remove로 지운다.차이는 삭제 비용 — PriorityQueue.remove(Object)는 선형 탐색이라 O(n)이다. TreeMap 쪽이 최악의 경우에 안전하다. 목차1 문제프로그래머스 #42628이중우선순위큐operations.length ≤ 1,000,000난이도: Lv.3최댓값과 최솟값을 모두 꺼낼 수 있는 큐를 구현하..

📌 핵심 요약야근 지수는 제곱 합 — 작업량 x를 1시간 처리하면 지수는 2x - 1만큼 줄어든다. 이 값은 x가 클수록 크다.매 시간 가장 큰 일감을 1 깎는다 — 최대 힙(PriorityQueue + reverseOrder)으로 최댓값을 꺼내 1 줄이고 다시 넣는다.제곱은 (long) x * x — Math.pow는 오차 보장이 1 ulp라 캐스팅 과정에서 1이 사라질 수 있다. 목차1 문제프로그래머스 #12927야근 지수n ≤ 1,000,000 · works.length ≤ 20,000난이도: Lv.3퇴근까지 남은 시간이 n시간이고, 각 일감의 작업량이 배열 works에 담겨 있다. 1시간에 아무 일감이나 하나를 골라 작업량을 1 줄일 수 있다. 퇴근 시점에 남아 있는 각 작업량을 제곱해 모두 더..