HackerRank/Mini-Max Sum

두 가지 방법이 있다.

1. 정렬 후, 0번째, 마지막 제외하고 더하면 최소 최대가 된다. nlogn + n = NlogN

2. 최소값, 최대값 찾은후 전부 더한다음 빼주면 그게 최소 최대값이 된다. n + n + n (최소탐색, 최대탐색, 더하기) = N

N이 빠르다. 2번이 좀 더 좋다. 문제에서 overflow 조심하랬소 64비트 쓰랬으니 long long 써준다.

void miniMaxSum(vector<int> arr) {
    sort(arr.begin(), arr.end());
    
    long long sum = 0;
    
    for(int i=0; i<arr.size()-1; ++i)
    {
        sum += arr[i];
    }
    
    sum = 0;
    for(int i=1; i<arr.size(); ++i)
    {
        sum += arr[i];
    }
    
    
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    
    //long long sum = 0;
    sum = 0;
    for(int i=0; i<arr.size(); ++i)
    {
        sum += arr[i];
    }
    
    cout << sum-max << " " << sum-min << endl;
}