[99클럽 코테 스터디 22일차 TIL] #힙4

벌써 어느덧 22일 차네요.. 어제 분명히 알바 다녀와서 블로그 쓰려고 했는데 너무 힘들어서 뻗어버렸어요.

뭔가 백준 스트릭 끊긴 것 같은 찝찝한 이 느낌,, 오늘이라도 열심히 써보겠습니다.

 

문제 설명

---

 

우선 처음보는 사이트에 영어로 된 문제였어서 처음엔 당황을 좀 했습니다; 근데 천천히 읽어보니 말하고자 하는 얘기는 쉽더라고요.

 

숫자로 된 배열 gifts와 수 k가 주어진 후, k만큼 반복해서 가장 큰 수의 제곱근을 배열에 넣어주고 가장 큰 수는 제거해 주는 간단한 문제였습니다.

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

 

 

생각 흐름

---

음.. 문제를 이해하고 나서는 의외로 쉬운 문제였어요.

 

숫자 배열을 받고 이 속에 있는 요소들의 크기를 비교해서 알아내야 하니까 우선순위 큐를 이용했습니다.

 

이를 통해서 수들을 내림차순으로 배열했고 pq.top()의 제곱근을 push 해주고 pq.top()은 삭제하며 pq를 재구성했고

이들의 요소들을 pq배열이 텅 빌 때까지 answer라는 변수에 합쳐서 저장해 주어서 마무리했습니다.

 

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {

        priority_queue<int> pq; // 크기 순으로 정렬위해 우선순위 큐 pq 선언
        for(auto i: gifts){ // 배열 요소들을 우선순위 큐에 저장
            pq.push(i);
        }
        long long int ans = 0;
        int x;
        while(k--){ 
            x = pq.top(); // 가장 큰 수 x
            pq.pop(); // 를 빼고
            pq.push(sqrt(x)); // x의 제곱근을 다시 넣어줌
        }
        while(!pq.empty()){ // 우선순위 큐가 빌 때까지
            ans += pq.top(); // ans에 더해주고
            pq.pop(); // 제거해주기
        }
        return ans;
    }
};

 

 

 

공부한 내용 정리

---

여기서 볼 만한 것은 제곱근 구하는 함수였던 것 같습니다.

 

1. sqrt() 함수

이 함수가 필요로 하는 헤더파일은 <cmath>라는 파일입니다.

 

이 함수는 매개변수로 들어온 숫자에 루트를 씌워서 계산한 값을 반환해 주는 역할을 합니다.

즉, 루트 매개변수 값을 구해준다고 생각하면 됩니다.

 

#include <cmath>

cout << sqrt(9); // 3