λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
✨ Algorithm

[λ°±μ€€/C++] 2108번: 톡계학

by nitronium102 2022. 7. 24.

문제

수λ₯Ό μ²˜λ¦¬ν•˜λŠ” 것은 ν†΅κ³„ν•™μ—μ„œ μƒλ‹Ήνžˆ μ€‘μš”ν•œ 일이닀. ν†΅κ³„ν•™μ—μ„œ N개의 수λ₯Ό λŒ€ν‘œν•˜λŠ” κΈ°λ³Έ ν†΅κ³„κ°’μ—λŠ” λ‹€μŒκ³Ό 같은 것듀이 μžˆλ‹€. λ‹¨, N은 ν™€μˆ˜λΌκ³  κ°€μ •ν•˜μž.

  1. μ‚°μˆ ν‰κ·  : N개의 μˆ˜λ“€μ˜ 합을 N으둜 λ‚˜λˆˆ κ°’
  2. 쀑앙값 : N개의 μˆ˜λ“€μ„ μ¦κ°€ν•˜λŠ” μˆœμ„œλ‘œ λ‚˜μ—΄ν–ˆμ„ 경우 κ·Έ 쀑앙에 μœ„μΉ˜ν•˜λŠ” κ°’
  3. μ΅œλΉˆκ°’ : N개의 μˆ˜λ“€ 쀑 κ°€μž₯ 많이 λ‚˜νƒ€λ‚˜λŠ” κ°’
  4. λ²”μœ„ : N개의 μˆ˜λ“€ 쀑 μ΅œλŒ“κ°’κ³Ό μ΅œμ†Ÿκ°’μ˜ 차이

N개의 μˆ˜κ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, λ„€ 가지 κΈ°λ³Έ 톡계값을 κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

첫째 쀄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진닀. 단, N은 ν™€μˆ˜μ΄λ‹€. κ·Έ λ‹€μŒ N개의 μ€„μ—λŠ” μ •μˆ˜λ“€μ΄ 주어진닀. μž…λ ₯λ˜λŠ” μ •μˆ˜μ˜ μ ˆλŒ“κ°’μ€ 4,000을 λ„˜μ§€ μ•ŠλŠ”λ‹€.

좜λ ₯

첫째 μ€„μ—λŠ” μ‚°μˆ ν‰κ· μ„ 좜λ ₯ν•œλ‹€. μ†Œμˆ˜μ  μ΄ν•˜ 첫째 μžλ¦¬μ—μ„œ λ°˜μ˜¬λ¦Όν•œ 값을 좜λ ₯ν•œλ‹€.

λ‘˜μ§Έ μ€„μ—λŠ” 쀑앙값을 좜λ ₯ν•œλ‹€.

μ…‹μ§Έ μ€„μ—λŠ” μ΅œλΉˆκ°’μ„ 좜λ ₯ν•œλ‹€. μ—¬λŸ¬ 개 μžˆμ„ λ•Œμ—λŠ” μ΅œλΉˆκ°’ 쀑 두 번째둜 μž‘μ€ 값을 좜λ ₯ν•œλ‹€.

λ„·μ§Έ μ€„μ—λŠ” λ²”μœ„λ₯Ό 좜λ ₯ν•œλ‹€.

풀이

1. μ‚°μˆ  평균 : μ‹€μˆ˜ μžλ£Œν˜• μ‚¬μš©

2. 쀑앙값 : n은 ν™€μˆ˜ -> 항상 (n/2)번째 인덱슀

3. μ΅œλΉˆκ°’: κ°€μž₯ 많이 λ‚˜νƒ€λ‚˜λŠ” 값이라고 μƒκ°ν•˜λ©΄ μ•ˆ λœλ‹€. μ—¬λŸ¬ 개 μžˆμ„ κ²½μš°λŠ” λ™μΌν•œ λΉˆλ„μˆ˜ λ‚΄μ—μ„œ 두 번째둜 μž‘μ€ 값을 좜λ ₯ν•˜κΈ° λ•Œλ¬Έ!

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

using namespace std;

typedef pair<int, int> ci;

bool cmp(const ci &a, const ci &b) {
    // 1. κ°œμˆ˜μ— λŒ€ν•΄ μ˜€λ¦„μ°¨μˆœ
    // 2. 값에 λŒ€ν•΄ λ‚΄λ¦Όμ°¨μˆœ
    if (a.second != b.second)
        return a.second > b.second;
    return a.first < b.first;
}

int findMode(int n, vector<int> &num) {
    vector<ci> count; // first : κ°’, second : 개수

    int cur_idx = 0;
    count.push_back({num[0], 1}); // 인덱슀 μ—λŸ¬ λ°©μ§€μš©

    // 이미 μ •λ ¬λœ λ²‘ν„°μ—μ„œ μ •μˆ˜μ˜ 개수λ₯Ό count -> μ—°μ†λ˜λŠ” 개수 count
    for (int i = 1; i < n; i++) {
        if (num[i] == num[i - 1]) // 연속인 경우
            count[cur_idx].second++;
        else {
            count.push_back({num[i], 1}); // μƒˆλ‘œμš΄ κ°’ μ‚½μž…
            cur_idx++;
        }
    }

    // λͺ¨λ‘ 1κ°œμ”© λ“€μ–΄μžˆλŠ” 경우
    if (cur_idx == 0)
        return num[0];

    // μ΅œλΉˆκ°’ 계산
    sort(count.begin(), count.end(), cmp);

    // μ—¬λŸ¬ 개인 경우
    if (count[0].second == count[1].second)
        return count[1].first;
    return count[0].first;
}

int main() {
    int n;
    int sum = 0;
    cin >> n;

    vector<int> num(n);
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        sum += num[i];
    }

    sort(num.begin(), num.end());

    if (round((double)sum / n) == -0)
        cout << "0\n";
    else
        cout << round((double)sum / n) << '\n';
    cout << num[n / 2] << "\n"; // 쀑앙값
    cout << findMode(n, num) << "\n"; // μ΅œλΉˆκ°’
    cout << num[n - 1] - num[0] << "\n"; // λ²”μœ„
}

λŒ“κΈ€