[BOJ 2587] 대표값2 - [수학, 구현, 정렬]

[BOJ 2587] 대표값2 - [수학, 구현, 정렬]

문제 링크

https://www.acmicpc.net/problem/2587

문제 요약

• 다섯 개의 자연수가 주어질 때, 이들의 평균과 중앙값을 구하는 프로그램 작성.
• 주어지는 수는 모두 100보다 작은 10의 배수임.

접근 방법

• 자료구조: std::vector<int> (5개의 정수를 저장하기 위한 동적 배열)
• 알고리즘: 정렬 (Sorting)
• 핵심 아이디어: - 평균은 모든 원소의 합을 개수(5)로 나누어 구함.
  • 중앙값은 배열을 오름차순으로 정렬했을 때 인덱스 2(세 번째)에 위치한 값임.

풀이 코드

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

using namespace std;

int main() {
    // 입출력 성능 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<int> numbers(5);
    int sum = 0;

    // 5개의 숫자를 입력받으며 합계를 계산
    for (int i = 0; i < 5; i++) {
        cin >> numbers[i];
        sum += numbers[i];
    }

    // 오름차순 정렬
    sort(numbers.begin(), numbers.end());

    // 출력: 평균(합/5)과 중앙값(정렬 후 3번째 원소)
    cout << sum / 5 << "\n";
    cout << numbers[2] << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N \log N)$ (여기서 $N=5$이므로 사실상 상수 시간 $O(1)$에 수렴)
• 공간 복잡도: $O(1)$ (크기가 5인 고정된 배열 사용)

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms (백준 제출 시스템 기준 예상치)

핵심 포인트

1. std::sort를 활용하여 중앙값을 찾기 위한 전제 조건인 정렬을 쉽게 해결할 수 있습니다.
2. 문제에서 주어지는 입력값이 10의 배수이므로 평균값 계산 시 나머지가 발생하지 않아 정수 나눗셈으로 충분합니다.

예제 확인

• 예제 1: - 입력: 10, 40, 30, 60, 30
  • 합계: 170 -> 평균: $170 / 5 = 34$
  • 정렬: 10, 30, 30, 40, 60 -> 중앙값: 30
  • 출력: 34, 30 (일치)