[SW Expert Academy] 10505번 C++ 풀이

SW Expert Academy 10505 - 소득불균형 문제입니다.

SW Expert Academy

시간 제한	메모리 제한	난이도
(C++ 기준)  TC 260개, 1초	힙, 정적 256MB, 스택 1MB	D3

 

23년 1월 초, 교내 코딩캠프를 다녀왔다. SW Expert Academy는 그곳에서 교수님이 알려준 사이트이다. 이후, 삼성sds 인스타그램에서 이벤트도 하길래 이 사이트의 문제를 풀어봤다. 이 문제는 SW Expert Academy에서 맨 처음 풀어보는 문제이다.

 

해당 문제를 요약하면, 주어진 수열에서 평균 이하인 원소의 개수를 세는 단순한 문제이다. 쉬운 문제지만, 백준때문에 하도 당해서 그런지, 260개의 테스트 케이스를 돌려서 1초가 나와야 한다는 것이 조금 맘에 걸렸다. 그래서 문제의 시간복잡도를 최대한 줄여보았다. 지금 글을 쓰는 시점에서 보니, 굳이 안해도 통과는 했을 것 같다.

 

각설하고, 시간복잡도를 최대한 줄이기 위해, 이분 탐색을 활용했다. 평균을 구하고, 정렬한 수열에서 평균을 초과하는 원소의 인덱스를 구하면 그것이 평균 이하의 개수일 것이다. 인덱스를 구하는 것은, std::distance 함수를 사용했다. std::distance 함수는 O(n)의 시간 복잡도를 가지지만, 특정 경우에서 O(1)로 동작한다. 함수 인자로 받는 iterator가 LegacyRandomAccessIterator 의 조건을 만족할 때인데, vector에서 사용하는 vector::iterator 가LegacyRandomAccessIterator이기 때문에, 상수 시간에 동작할 수 있다(https://en.cppreference.com/w/cpp/iterator/distance). 따라서 인덱스를 구하는 것도 빠르게 구했다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define ALL(X) X.begin(), X.end()
using namespace std;

int N;
vector<int> money;

void input() {
    cin >> N;
    money.resize(N);
    for(int& x : money) cin >> x;
}

void sol(int tc, int avg) {
    int avg = accumulate(ALL(money), 0) / N;
    sort(ALL(money));
    
    cout << "#" << tc << " " << distance(money.begin(), upper_bound(ALL(money), avg)) << endl;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_case;
    int T;
    // freopen("input.txt", "r", stdin);

    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case) {
        input();
        sol(test_case);
    }
}