[99클럽 22일차] [LeetCode] 2558 Take Gifts From the Richest Pile

문제 설명

• 배열 gifts에서 가장 큰 값을 반복적으로 제곱근으로 줄인 후, 최종 배열의 값을 모두 더한다.
• 매번 가장 큰 값을 효율적으로 찾아야 하고 이걸 k번 반복

제약 조건

• 1 ≤ gifts.length ≤ 1,000
• 1 ≤ k ≤ 1,000
• 1 ≤ gifts[i] ≤ 10^6

문제 접근

우선순위 큐 사용

• 우선순위 큐(Priority Queue)를 활용하여 항상 가장 큰 값을 빠르게 관리
• 내림차순 우선순위 큐로 구성하여 삽입과 꺼내기가 효율적($O(\log n)$).

최종 코드

import java.util.*;

class Solution {
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long answer = 0;

        for (int g : gifts) {
            pq.offer(g);
        }

        for (int i = 0; i < k; i++) {
            int max = pq.poll();
            pq.offer((int) Math.sqrt(max));
        }

        while (!pq.isEmpty()) {
            answer += pq.poll();
        }

        return answer;
    }
}

회고

문제를 처음에 풀면서 요새 계속 우선순위큐 자료구조를 사용하다보니 최소값, 최대값 찾을 때 써야겠다는 느낌이 바로 온다.
그런데 이번에 sqrt 쓰면서 함수 이름이 기억이 안나서 거기에서 시간을 좀 잡아먹었다ㅠㅠ IDE에 익숙해져 있다가 코테공부하면서 쓰려고 하면 종종 까먹는다.. 자주 쓰다보면 손에 익겠지