백준 2108 통계학

참으로 허탈한 문제. 아무리 생각해도 충분한 시간복잡도에 통과할 수 있는데, 시간초과가 났다. 그래서 개선된 속도로 풀어도 시간초과가 났는데.. 알고보니 입출력 시간 문제였다.

세 번으로 나누어서 풀었다. 처음이 가장 복잡도가 안좋은 방법. 그러더라도 문제를 풀기엔 충분한 스펙이였다. 문제는 입력 시간이였다.

import sys
input = sys.stdin.readline

_n = int(input())
l = [ int(input()) for _ in range(_n) ]

print( round(sum(l)/len(l)) )

sorted = [ f for f in l ]
sorted.sort()
print( sorted[_n//2] )

f = { }
d = 0
for i in l:
    s = f.get(i, 0)
    f[i] = s + 1
    if d < f[i]:
        d = f[i]

d = [ i for i, j in f.items() if j == d]
d.sort()
if len(d) > 1:
    d = d[1]
else:
    d = d[0]
print(d)

print(sorted[_n-1]-sorted[0])

2번째 방법

import sys
input = sys.stdin.readline
# print = sys.stdout.write

_n = int(input())
list = []
for i in range(_n):
    d = int(input())
    list.append(d)

sorted = [ 0 ] * 8001
for n in list:
    sorted[n + 4000 ] += 1

ans = 0
for idx, n in enumerate(sorted):
    ans += (idx - 4000) * n

print( round(ans / _n) )

mid = _n // 2 + (1 if _n%2 else 0)
for idx, n in enumerate(sorted):
    mid -= n
    if mid <= 0 :
        print( idx - 4000 )
        break

mx = 0
for idx, n in enumerate(sorted):
    if mx < n:
        mx = n

non = 0
cnt = 2
for idx, n in enumerate(sorted):
    if n == mx:
        cnt -= 1
        non = idx
        if cnt == 0:
            print( idx - 4000 )
            break

if cnt == 1:
    print( non - 4000 )

mx = 8000
mn = 0
while mx >= 0:
    if sorted[mx] > 0:
        break
    mx -= 1

while mn <= 8000:
    if sorted[mn] > 0:
        break
    mn += 1

print(mx - mn)

마지막은 c++

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int main() {
int n;
    cin >> n;

    vector<int> v(8001, 0);
    for (int i =0; i<n; i++) {
        int temp;
        cin >> temp;
        v[temp+4000] += 1;
    }

    int sum = 0;
    for (int i=0; i<=8000; i++) {
        sum += (i - 4000)* v[i];
    }
    cout << (int)round(double(sum) / n ) << "\n";

    int mid = n/2  + (n%2?1:0); 
    for (int i=0; i<=8000; i++) {
        mid -= v[i];
        if (mid <=0){
            cout << (i - 4000) <<"\n";
            break;
        }
    }

    int d = 0;
    for (int i=0; i<=8000; i++) {
        if (d < v[i]) {
            d = v[i];
        }
    }

    int non = 0;
    int cnt = 2;
    for (int i=0; i<=8000; i++) {
        if (d == v[i]) {
            non = i - 4000;
            cnt--;
            if (cnt == 0) {
                cout << i - 4000 << "\n";
                break;
            }
        }
    }

    if (cnt == 1) {
        cout << non << "\n";
    }

    int mx = 8000;
    int mn = 0;
    while (mx >= 0){
        if(v[mx]>0) break;
        mx--;
    }

    while (mn <= 8000) {
        if (v[mn]>0) break;
        mn++;
    }
    cout << mx - mn <<"\n";
}