문제
각 테스트 케이스마다 학생들의 점수가 주어질 때, 평균을 넘는 학생의 비율을 구하라.
입력
테스트 케이스 수, 각 케이스에 학생 수와 점수가 주어진다.
출력
각 테스트 케이스마다 평균을 넘는 학생의 비율을 소수점 셋째 자리까지 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 5 50 50 70 80 100 7 100 95 90 80 70 60 50 3 70 90 80 3 70 90 81 9 100 99 98 97 96 95 94 93 91 | 40.000% 57.143% 33.333% 66.667% 55.556% |
풀이
각 케이스의 평균을 구하고, 평균을 초과하는 학생 수의 비율을 계산한다.
- N개의 점수 합을 구하여 평균을 계산한다
- 평균보다 큰 점수를 가진 학생 수를 센다
- (초과 학생 수 / N) * 100을 소수점 셋째 자리까지 출력한다
핵심 아이디어: 평균을 먼저 계산한 뒤, 한 번 더 순회하며 초과 학생을 세면 O(N)에 해결된다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day548BOJ4344평균은넘겠지 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] arr;
int testcase = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < testcase; i++) {
st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
arr = new int[N];
double sum = 0;
for (int j = 0; j < N; j++) {
int val = Integer.parseInt(st.nextToken());
arr[j] = val;
sum += val;
}
double mean = (sum / N);
double count = 0;
for (int j = 0; j < N; j++) {
if (arr[j] > mean) {
count++;
}
}
System.out.printf("%.3f%%\n", (count / N) * 100);
}
}
}복잡도
- 시간: O(T * N)
- 공간: O(N)