자료구조 - 백준 1546

백준 1546 - 평균 구하기

1. 문제 분석

• 기말고사 점수 중에 최댓값 M을 고르고, 모든 점수를 /M X 100 으로 바꾼다
  → 최고점 70점, 수학 점수 50점이면 수학 점수는 50/70 X 100으로 바꾸는 것

위 방법 대로 새로 계산했을 때 새로운 평균을 구하는 것이 문제

2. 입력

• 첫째 줄에는 시험 본 과목의 개수 N / 범위는 (N <= 1000)
• 둘째 줄에는 현재 성적 / 범위는 (0 <= 점수 <= 100), 적어도 하나의 값은 0보다 큼

3. 출력

• 실제 정답과 출력값이 절대오차 또는 상대오차가 10^-2 이하면 정답

4. 시간/공간 복잡도 분석

시간 복잡도 분석

• 최댓값을 찾기 위해 배열을 N번 순회, 조작한 점수의 평균을 계산하기 위해 N번 다시 반복하니까 → O(N)

공간 복잡도 분석

• 배열의 크기가 N인 것을 사용해하니 → O(N)

5. 슈도 코드

1. 과목 개수 N 입력 받기, N개 점수 받기
2. for(N개 길이만큼 반복) {
	2-1. score 배열에 점수 저장
    2-2. 최댓값 M 찾기
}
3. for(N개 길이만큼 반복) {
	3-1. 조작된 점수 총합 sum(누적합)
}
4. 평균 출력

6. 코드 구현

package dataSource;

import java.io.*;
import java.util.*;

public class No_1546 {
	public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //과목 개수 N 입력
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int score[] = new int[N];
        int M = 0;
        double sum = 0;
        
        for (int i = 0; i < N; i++) {
        	score[i] = Integer.parseInt(st.nextToken());
        	if(score[i] > M) {
        		M = score[i];
        	}
        }
       
       for (int i = 0; i < N; i++) {
    	   sum += (double) score[i] / M * 100;
       }
       
       System.out.println(sum / N);
	}
}