문제 링크

내 코드

0ms, 13MB

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> pq;
        for(int gift : gifts) pq.push(gift);

        while(!pq.empty() && k) {
            auto now = pq.top(); 
            if(now == 1) break; // no need to keep going
            pq.pop(); --k;
            pq.push(static_cast<int>(sqrt(now)));
        }

        long long answer{};
        while(!pq.empty()) {
            answer += static_cast<long long>(pq.top());
            pq.pop();
        }
        return answer;
    }
};

Solution

Approach 1: Brute Force

• 11ms, 12.89MB
• Complexity
  • Let $n$ be the size of the gifts array.
  • Time Complexity: $O(k \times n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        int n = gifts.size();

        // Perform the operation k times
        for (int i = 0; i < k; i++) {
            // Initialize the index of the richest pile (maximum element)
            int richestPileIndex = 0;

            // Iterate through the array to find the index of the maximum
            // element
            for (int currentPileIndex = 0; currentPileIndex < n;
                 currentPileIndex++) {
                // If we find a new maximum, update the index
                if (gifts[richestPileIndex] < gifts[currentPileIndex]) {
                    richestPileIndex = currentPileIndex;
                }
            }

            // Replace the richest pile with the floor of its square root
            gifts[richestPileIndex] = sqrt(gifts[richestPileIndex]);
        }

        // Calculate the sum of the remaining gifts in the array
        long long int numberOfRemainingGifts =
            accumulate(gifts.begin(), gifts.end(), 0LL);

        return numberOfRemainingGifts;
    }
};

GPT

이 코드는 다음과 같은 문제 상황을 다룹니다:

• gifts라는 배열이 있고, 각 원소는 어떤 “선물 더미(pile)“에 담긴 선물의 개수를 나타냅니다.

• 특정한 연산을 k번 반복합니다. 이 연산은:

  1. 현재 gifts 배열에서 가장 많은 선물을 가진 더미(최댓값 원소)를 찾는다.
  2. 그 최댓값을 가진 원소를 그 값의 제곱근의 내림(floor) 값으로 바꾼다.

• 모든 연산을 마친 뒤, 남아있는 선물들의 총합을 구하여 반환합니다.

자세한 동작 과정:

1. 입력 파악:
   gifts 배열에는 여러 더미의 선물 개수가 들어 있으며, k는 연산을 수행할 횟수를 의미합니다.

2. 연산 반복 (k회):

   for (int i = 0; i < k; i++) {
       int richestPileIndex = 0;
   
       // 가장 선물이 많은 더미의 인덱스를 찾기
       for (int currentPileIndex = 0; currentPileIndex < n; currentPileIndex++) {
           if (gifts[richestPileIndex] < gifts[currentPileIndex]) {
               richestPileIndex = currentPileIndex;
           }
       }
   
       // richestPileIndex 위치에 있는 선물 더미를 sqrt 내림 처리
       gifts[richestPileIndex] = (int)sqrt(gifts[richestPileIndex]);
   }

   각 단계에서:

   • richestPileIndex를 0으로 초기화하고, gifts를 순회하면서 가장 큰 값을 가진 인덱스를 찾습니다.
   • 찾은 인덱스의 값(가장 많은 선물을 가진 더미)을 그 값의 제곱근을 구한 뒤 정수로 내림하여 업데이트합니다. (예: 100개의 선물 -> sqrt(100)=10개, 37개의 선물 -> sqrt(37)≈6.08… 내림하면 6개)

   이 과정을 k번 반복하면, 매번 가장 많은 선물을 가진 더미를 좀 더 줄여나가는 효과가 있습니다.

3. 최종 합계 계산:

   long long int numberOfRemainingGifts = accumulate(gifts.begin(), gifts.end(), 0LL);

   모든 연산을 마친 뒤, 수정된 gifts 배열의 모든 원소(남아있는 선물 수)를 더해 총합을 구합니다.

4. 결과 반환:

   return numberOfRemainingGifts;

   남아있는 선물의 총합을 반환합니다.

복잡도 및 개선점:

• 현재 매 연산(k회)마다 n번을 순회하여 최대값을 찾습니다. 따라서 시간 복잡도는 O(k*n)이 됩니다.
• k와 n이 크다면 비효율적입니다.
• 이를 효율적으로 개선하려면 최대 힙(priority queue)을 사용하여 O(log n)에 최대값을 얻고 업데이트할 수 있습니다. 그럴 경우 복잡도가 O(k log n)으로 개선됩니다. 하지만 현재 제공된 코드는 단순한 방법으로 구현되어 있습니다.

정리:
이 코드는 주어진 배열에서 k번에 걸쳐 가장 큰 값을 제곱근 내림 값으로 교체하고, 최종 합을 구하는 단순 구현입니다.

Approach 2: Sorted Array

• 1ms, 13.34MB
• Complexity
  • Let $n$ be the size of the gifts array.
  • Time Complexity: $O(k \times (n + \log n))$
  • Space Complexity: $O(n)$

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        int n = gifts.size();

        // Create a copy of the gifts array and sort it
        vector<int> sortedGifts = gifts;
        sort(sortedGifts.begin(), sortedGifts.end());

        // Perform the operation k times
        for (int i = 0; i < k; i++) {
            int maxElement = sortedGifts[n - 1];
            sortedGifts.pop_back();

            // upper_bound returns the first element greater than
            // sqrt(maxElement)
            auto spotOfSqrt = upper_bound(sortedGifts.begin(),
                                          sortedGifts.end(), sqrt(maxElement));

            // Insert the square root value at the found position
            sortedGifts.emplace(spotOfSqrt, sqrt(maxElement));
        }

        // Calculate the sum of the remaining gifts in the array
        long long int numberOfRemainingGifts =
            accumulate(sortedGifts.begin(), sortedGifts.end(), 0LL);

        return numberOfRemainingGifts;
    }
};

GPT

이 코드는 이전 코드들과 비슷한 문제를 해결하지만, 매번 최대값을 찾기 위해 정렬 상태를 유지하는 방식으로 구현한 예시입니다. 핵심은 sortedGifts 배열을 항상 정렬 상태로 유지하면서, 가장 큰 값을 꺼내고 그 제곱근을 다시 적절한 위치에 삽입하는 과정을 k번 반복하는 것입니다.

상세 동작 과정:

1. 초기 정렬:

   vector<int> sortedGifts = gifts;
   sort(sortedGifts.begin(), sortedGifts.end());

   처음부터 gifts를 정렬하여 sortedGifts에 저장합니다. 가장 큰 값은 항상 sortedGifts의 끝에 위치하게 됩니다.

2. k번의 연산:

   for (int i = 0; i < k; i++) {
       int maxElement = sortedGifts[n - 1];   // 가장 큰 값 (마지막 원소)
       sortedGifts.pop_back();                // 이를 제거
       
       // 제곱근을 구해 sqrtValue에 저장
       int sqrtValue = (int)sqrt(maxElement);
   
       // sqrtValue를 삽입할 위치를 upper_bound로 찾는다
       // upper_bound(sortedGifts.begin(), sortedGifts.end(), sqrtValue)는
       // sqrtValue보다 큰 값이 처음으로 나타나는 위치를 반환
       auto spotOfSqrt = upper_bound(sortedGifts.begin(), sortedGifts.end(), sqrtValue);
       
       // 해당 위치에 sqrtValue를 삽입하여 배열을 다시 정렬 상태 유지
       sortedGifts.emplace(spotOfSqrt, sqrtValue);
   }

   • 매번 가장 큰 원소를 제거한 뒤, 그 원소의 제곱근을 올바른 위치에 삽입합니다.
   • upper_bound를 사용하면 O(log n)에 위치를 찾을 수 있지만, 벡터에 삽입하는 과정은 내부적으로 원소를 이동시키므로 최악 O(n)이 걸립니다. 따라서 전체 복잡도는 여전히 비효율적일 수 있습니다.
   • 이 방식은 항상 sortedGifts를 정렬 상태로 유지하기 때문에, 다음 반복에서 최대값(가장 끝 원소)와 다시 삽입할 위치를 쉽게 찾을 수 있습니다.

3. 최종 합 계산:

   long long numberOfRemainingGifts = accumulate(sortedGifts.begin(), sortedGifts.end(), 0LL);
   return numberOfRemainingGifts;

   모든 연산을 마친 후, sortedGifts에 남아있는 모든 값들을 더해 최종 결과를 반환합니다.

정리:

• 이 코드는 매번 최대값을 제거하고 그 제곱근 값을 올바른 위치에 삽입하는 과정을 통해 배열의 정렬 상태를 유지합니다.
• upper_bound를 통해 적절한 삽입 위치를 찾고, emplace를 통해 그 위치에 제곱근 값을 삽입합니다.
• 최종적으로 남은 선물들의 총합을 반환합니다.

단점은 매번 벡터 중간에 삽입하는 과정에서 O(n)의 비용이 들어 비효율적이라는 점이며, 이를 개선하려면 힙이나 다른 자료구조(예: balanced tree, multiset)를 사용하는 것이 좋습니다.

Approach 3: Heap

• 3ms, 13.48MB
• Complexity
  • Let $n$ be the size of the gifts array.
  • Time Complexity: $O(n + k \times \log n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        // Create a max-heap from the 'gifts' array (using a priority_queue)
        priority_queue<int> giftsHeap(gifts.begin(), gifts.end());

        // Perform the operation 'k' times
        for (int i = 0; i < k; i++) {
            // Get the maximum element from the heap (top element)
            int maxElement = giftsHeap.top();
            giftsHeap.pop();

            // Insert the floor of the square root of the maximum element back
            // into the heap
            giftsHeap.push(sqrt(maxElement));
        }

        // Accumulate the sum of the elements in the heap
        long long numberOfRemainingGifts = 0;
        while (!giftsHeap.empty()) {
            numberOfRemainingGifts += giftsHeap.top();
            giftsHeap.pop();
        }
        return numberOfRemainingGifts;
    }
};

GPT

이 코드는 주어진 배열 gifts에서 다음 과정을 k번 반복한 뒤, 남은 모든 값의 합을 구하는 문제를 효율적으로 해결하는 방식 중 하나입니다. 여기서의 연산 과정은 다음과 같습니다:

1. 현재 gifts 배열(또는 힙)에서 가장 큰 값을 뽑는다.
2. 그 값을 제곱근을 취한 뒤, 내림(floor)한 값으로 다시 넣는다.
3. 이 과정을 k번 반복한 후, 최종적으로 남아있는 모든 값의 합을 구한다.

구현 상세:

1. 최대 힙 구성:

   priority_queue<int> giftsHeap(gifts.begin(), gifts.end());

   priority_queue<int>는 기본적으로 최대 힙을 형성합니다.
   즉, 가장 큰 값이 giftsHeap.top()으로 접근할 수 있어, 매번 O(1)에 최대값을 얻을 수 있습니다.

2. k번의 연산 수행:

   for (int i = 0; i < k; i++) {
       int maxElement = giftsHeap.top();
       giftsHeap.pop();
   
       giftsHeap.push((int)sqrt(maxElement));
   }

   • giftsHeap.top()을 통해 현재 힙에서 가장 큰 값을 가져옵니다.
   • giftsHeap.pop()으로 이 값을 힙에서 제거합니다.
   • 제거한 최대값 maxElement에 대해 sqrt(maxElement)를 취한 뒤, 정수로 형변환(내림)하여 다시 힙에 넣습니다(giftsHeap.push(...)).

   이로써 기존 최대값이 더 작은 값(그 제곱근)으로 대체되며, 힙은 계속해서 정렬 상태를 유지합니다.
   이 연산은 총 k번 반복됩니다.

3. 최종 합 계산:

   long long numberOfRemainingGifts = 0;
   while (!giftsHeap.empty()) {
       numberOfRemainingGifts += giftsHeap.top();
       giftsHeap.pop();
   }

   모든 연산이 끝난 후, 힙에 남아 있는 모든 값들을 꺼내어 합을 구합니다.
   여기서 while 루프를 돌며 giftsHeap.top() 값을 하나씩 더한 뒤 pop하여 최종 합을 계산합니다.

복잡도 분석:

• 힙을 구성하는 것은 O(n)이며,
• 최대값을 꺼내고 다시 삽입하는 연산을 k번 반복할 때 각 연산은 O(log n) (힙에서 pop과 push 연산) 정도의 시간 복잡도를 가집니다.
• 따라서 전체 시간 복잡도는 대략 O(n + k log n) 정도로, 단순히 매번 최댓값을 찾기 위해 전체 배열을 스캔하는 O(k*n) 방법보다 훨씬 효율적입니다.

정리:

• 이 코드는 최대 힙을 사용하여 매번 가장 큰 값을 효율적으로 꺼내고, 그 값을 제곱근으로 대체하는 과정을 반복합니다.
• 모든 연산 후 남은 값들의 합을 구해 반환합니다.
• 힙을 사용함으로써 매번 최대값을 찾는 과정을 효율적으로 처리할 수 있습니다.