23.05.01. 풀었던 문제들

Leetcode 1491. Average Salary Excluding the Minimum and Maximum Salary

 주어진 배열에서 max값, min값을 뺀 값들의 평균을 구하는 문제. 전체를 sort하고 min, max값만 빼고 평균 구해도 되지만 그러면 시간복잡도가 O(nlogn)이다. 그냥 한 번 순회하면서 min, max값, sum 구하고 구하는 게 나을 거라 생각했다.

// Runtime 0 ms Beats 100%
// Memory 7 MB Beats 98.74%

typedef long long ll;
class Solution {
public:
    double average(vector<int>& salary) {
        ll sum = 0, minValue = INT_MAX, maxValue = INT_MIN;
        for(int s : salary){
            minValue = min(minValue, (ll)s);
            maxValue = max(maxValue, (ll)s);
            sum += s;
        }
        sum = sum - minValue - maxValue;
        return (double)sum / (salary.size() - 2);
    }
};

 

시간복잡도

 처음부터 끝까지 1번 순회하므로 O(n)

 

공간복잡도

 별다른 추가공간 사용하지 않음 O(1)