문제 링크

내 코드

0ms, 27.2MB

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        for(int i{};i<k;++i) {
            int minValue = 1 << 30, minIndex = -1;
            for(int j{}, n{static_cast<int>(nums.size())};j<n;++j) {
                if(minValue > nums[j]) {
                    minValue = nums[j];
                    minIndex = j;
                }
            }
            nums[minIndex] *= multiplier;
        } 
        return nums;
    }
};

Solution

Approach 1: K Full Array Scans for Minimum Element Multiplication

• 0ms, 27.06MB
• Complexity
  • Let $N$ be the length of nums.
  • Time Complexity: $O(N \cdot k)$
  • Space Complexity: $O(1)$

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        int n = nums.size();

        while (k--) {
            // Find the index of the smallest element in the array
            int minIndex = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] < nums[minIndex]) {
                    minIndex = i;
                }
            }

            // Multiply the smallest element by the multiplier
            nums[minIndex] *= multiplier;
        }

        return nums;
    }
};

GPT

아래 코드는 다음과 같은 로직으로 동작합니다:

1. 파라미터

   • nums: 원소들을 담고 있는 정수 벡터
   • k: “가장 작은 원소를 찾고 곱셈을 수행”하는 과정을 반복할 횟수
   • multiplier: 가장 작은 원소에 곱할 값

2. 반복문(while (k--))

   • k가 0이 될 때까지(즉, k번 반복) 다음 과정을 수행합니다:

     1. 가장 작은 원소의 인덱스 찾기

        int minIndex = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }

        • minIndex를 0으로 초기화한 뒤, 모든 원소를 순회하면서 nums[i]가 nums[minIndex]보다 작으면 minIndex를 i로 갱신합니다.
        • 반복이 끝나면 nums[minIndex]는 전체 원소 중 최솟값이 됩니다.

     2. 가장 작은 원소에 multiplier 곱하기

        nums[minIndex] *= multiplier;

        • 찾은 가장 작은 원소를 multiplier로 곱하여 업데이트합니다.

3. 결과 반환

   • 모든 반복을 마치면 최종적으로 업데이트된 벡터 nums를 반환합니다.

---

핵심 포인트

• 매번 반복마다 가장 작은 원소 한 개를 찾아 multiplier를 곱합니다.
• 따라서, 만약 multiplier가 음수라면 원소가 음수가 되어 버릴 수도 있고, 0이면 원소를 0으로 만들 수도 있습니다.
• k번 반복한 뒤의 벡터 상태가 최종 결과가 됩니다.

Approach 2: Heap-Optimized K Minimum Value Multiplication

• 3ms, 27.7MB
• Complexity
  • Let $N$ be the length of nums.
  • Time Complexity: $O(N + k \cdot \log N)$
  • Space Complexity: $O(N)$

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        vector<pair<int, int>> heap;
        for (int i = 0; i < nums.size(); i++) {
            heap.push_back({nums[i], i});
        }

        make_heap(heap.begin(), heap.end(), greater<>());

        while (k--) {
            pop_heap(heap.begin(), heap.end(), greater<>());
            auto [value, i] = heap.back();
            heap.pop_back();

            nums[i] *= multiplier;
            heap.push_back({nums[i], i});
            push_heap(heap.begin(), heap.end(), greater<>());
        }

        return nums;
    }
};

GPT

아래 코드는 최소 힙(min-heap) 을 사용하여, k번 반복하면서 벡터 nums의 가장 작은 원소에 multiplier를 곱하는 로직을 구현한 예시입니다. 전체적인 흐름을 단계별로 살펴보겠습니다.

---

코드 분석

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        vector<pair<int, int>> heap;

        // 1. 초기 힙(배열) 구성
        for (int i = 0; i < nums.size(); i++) {
            heap.push_back({nums[i], i});
        }

        // 2. make_heap()을 이용해 min-heap 생성
        make_heap(heap.begin(), heap.end(), greater<>());

        // 3. k번 반복
        while (k--) {
            // 3-1. 힙에서 최소값(루트 노드)을 pop
            pop_heap(heap.begin(), heap.end(), greater<>());
            auto [value, i] = heap.back();
            heap.pop_back();

            // 3-2. nums[i]에 multiplier 곱해주기
            nums[i] *= multiplier;

            // 3-3. 다시 힙에 push
            heap.push_back({nums[i], i});
            push_heap(heap.begin(), heap.end(), greater<>());
        }

        // 4. 최종 벡터 반환
        return nums;
    }
};

1. 초기 힙(배열) 구성

vector<pair<int, int>> heap;
for (int i = 0; i < nums.size(); i++) {
    heap.push_back({nums[i], i});
}

• (값, 인덱스) 형태로 pair를 만든 뒤 heap 벡터에 넣어줍니다.
• 이렇게 하면, 원소의 실제 값과 해당 원소가 nums 배열에서 몇 번째 위치인지(i)를 함께 관리할 수 있습니다.

2. make_heap(heap.begin(), heap.end(), greater<>())

• 표준 라이브러리의 make_heap 함수를 이용해, heap 벡터를 힙 자료구조로 만듭니다.
• greater<>()를 사용해 최소 힙(min-heap) 을 구성합니다.
  • 참고로, C++ 표준 라이브러리는 기본적으로 less<>()를 사용해 최대 힙(max-heap) 을 구성합니다.
  • greater<>()를 전달함으로써 “루트에 최소값이 오도록” 설정하는 것입니다.

3. k번 반복

while (k--) {
    pop_heap(heap.begin(), heap.end(), greater<>());
    auto [value, i] = heap.back();
    heap.pop_back();

    nums[i] *= multiplier;

    heap.push_back({nums[i], i});
    push_heap(heap.begin(), heap.end(), greater<>());
}

• 3-1. 최소값 꺼내기
  • pop_heap으로 최소 힙의 루트(가장 작은 값)를 벡터의 끝으로 보내고, heap.back()을 통해 최소값을 가져옵니다.
  • heap.pop_back()로 해당 원소를 힙에서 완전히 제거합니다.
• 3-2. 원소 업데이트
  • nums[i]에 multiplier를 곱해줍니다.
  • 이렇게 하면 “가장 작은 값”에 해당하는 원소가 변경됩니다.
• 3-3. 힙에 다시 넣기
  • 변경된 값( nums[i])을 {nums[i], i} 형태로 다시 힙에 삽입하고,
  • push_heap으로 최소 힙의 성질을 다시 유지시킵니다.

4. 최종 결과 반환

• 모든 반복이 끝나면, 힙 구조와는 별개로 실제 변경된 nums 벡터를 반환합니다.

---

요약

• 최소 힙을 사용하여 매번 k번 반복할 때마다 가장 작은 원소를 효율적으로 꺼내고(pop_heap), 해당 원소에 multiplier를 곱한 뒤 다시 힙에 넣는(push_heap) 과정을 수행합니다.
• 결과적으로, 가장 작은 원소를 k번 찾아서 곱해준 뒤 변경된 nums 벡터가 반환됩니다.