항해 99클럽 코딩테스트 스터디 22일차 TIL (자바 / 비기너)

<오늘의 학습 키워드>

- 우선순위 큐

<오늘의 문제>

제목 : 리트코드 /  2558. Take Gifts From the Richest Pile

https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/

<풀이>

정답은 더보기

import java.util.Collections;
import java.util.PriorityQueue;

public class Test {

    public static void main(String[] args) {
        System.out.println(pickGifts(new int[]{25,64,9,4,100}, 4));
    }

    public static long pickGifts(int[] gifts, int k) {

        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

        for (int i : gifts) {
            queue.add(i);
        }

        for (int i = 0; i < k; i++) {
            double maxGift = (double) queue.poll();
            queue.add((int) Math.sqrt(maxGift));
        }

        long answer = 0;

        for (int i : queue) {
            answer += i;
        }

        return answer;
    }
}

 

• 우선순위 큐를 내림차순으로 생성
• 배열의 값들을 큐에 삽입
• head에 있는 값(제일 큰 값들)을 하나씩 꺼내서 제곱근 계산 후 다시 큐에 삽입 -> k번 반복
• k번 반복에 끝난 뒤 큐의 숫자들을 전부 더한 값을 반환

<결론, 주의할점>