C++로 리스트의 모든 값을 같게 만드는 최소 연산 횟수 구하기

문제 설명

정수로 이루어진 리스트 nums가 있다고 가정해 봅시다. 사용할 수 있는 연산은 리스트에서 일부 정수들을 선택해 선택된 모든 값을 한 번에 1씩 증가시키는 것입니다. 이때 리스트의 모든 값을 서로 같게 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다.

예를 들어 입력이 [1, 3, 5]라면 출력은 4가 됩니다.

접근 방법

이 문제의 핵심은 의외로 단순합니다. 바로 최댓값과 최솟값의 차이(max − min)가 곧 정답이라는 점입니다.

그 이유는 다음과 같습니다.

• 리스트에서 가장 작은 값은 다른 값들과 같아지려면 결국 최댓값에 도달해야 하므로, 최소한 (최댓값 − 최솟값)번의 증가가 필요합니다. 따라서 연산 횟수는 적어도 (max − min)번 이상이어야 합니다.
• 반대로, 매번 아직 최댓값보다 작은 원소들을 모두 골라 1씩 증가시키면 정확히 (max − min)번 만에 모든 값을 같게 만들 수 있습니다.

따라서 필요한 최소 연산 횟수는 maxVal − minVal 입니다.

풀이 단계

• nums의 크기가 1이면 이미 모든 값이 같으므로 0을 반환합니다.
• ret := 0으로 초기화합니다.
• maxVal := -inf, minVal := inf로 초기화합니다.
• i := 0부터 시작해 i < nums의 크기를 만족하는 동안 i를 1씩 증가시키며 반복합니다.
  - maxVal := maxVal과 nums[i] 중 더 큰 값
  - minVal := minVal과 nums[i] 중 더 작은 값
• 반복이 끝나면 maxVal − minVal을 반환합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<int> &nums) {
        if (nums.size() == 1)
            return 0;
        int ret = 0;
        int maxVal = INT_MIN;
        int minVal = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            maxVal = max(maxVal, nums[i]);
            minVal = min(minVal, nums[i]);
        }
        return maxVal - minVal;
    }
};
int main() {
    Solution ob;
    vector<int> v = {1,3,5};
    cout << (ob.solve(v));
}

입력

{1,3,5}

출력

4

복잡도 분석

리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 상수 개수의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 입력 크기와 관계없이 매우 효율적으로 동작하는 솔루션입니다.