Study/Baekjoon

Baekjoon2108: 통계학

devyoseph 2021. 11. 9. 19:43

통계학

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초 256 MB 63879 16133 12989 26.833%

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

  1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
  2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
  3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
  4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

 

풀이

지금까지 주어진 입력값과는 다르게 음수가 포함되어있다. 하지만 절대값의 크기가 4000이하인 수들로 이루어져있다.

' 입력값이 제한된 정렬  = 카운팅 정렬 ' 을 떠올릴 수 있다. 음수 인덱스가 없는데 어떻게 배열에 저장하는가 생각할 수 있지만

음수를 양수화해서 저장하면 해결된다. [8000]크기의 배열을 만들고 4000번째 인덱스를 기준으로 음수와 양수를 같이 저장하는 것이다.

예를 들어 -500값을 입력받는 경우 4000을 더한 3500번째 index에 1을 추가하면 된다.

산술평균 / 범위 는 입력값을 카운팅 배열에 넣어주면서 구할 수 있고

중앙값 / 최빈값은 카운팅 배열을 모두 채운 이후 반복문을 통해 구할 수 있다.

최빈값의 조건을 만족하기 위해 최빈값을 새로 발견하는 순간 [2]크기의 배열을 만들고 [0]번 인덱스에 집어넣는다.

이후 똑같은 최빈값을 발견하면 [1]번 인덱스에 그 숫자를 집어넣는다(다시 최빈값을 새로 발견하면 초기화).

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   int[] count = new int[8001]; // -4000~+4000을 저장
	   Integer[] mode = null; //최빈값을 담는 곳 처음값과 그다음으로 작은 값이 들어간다
	   int N = Integer.parseInt(br.readLine());
	   int max=-4000,min=4000,many=-1, center=0,middle=0; //최대값, 최소값, 카운팅배열 중 가장 큰 값; 중앙값
	   
	   double sum=0.0; //평균을 계산하기 위한 합
	   
	   for(int i=0; i<N;i++) {
		   int num=Integer.parseInt(br.readLine());
		   
		   sum+=num; //입력값을 받으면서 sum에 계속 더한다
		   
		   if(num<min)min=num; 
		   if(num>max)max=num; //최대 최소를 기록
		   
		   count[num+4000]++; //음수를 고려해 모든 수에 4000을 더해 저장
	   }
	   
	   double avg = sum/N; //평균을 계산
	    boolean needMiddle =true; //중간값은 한번만 구하면 된다
	   for(int i=0; i<8001;i++) { //카운팅 배열 탐색
		   
		   center+=count[i]; //카운팅배열에서 누적합을 계산하고
		   
		if(center>=N/2+1 && needMiddle) { //중앙값 가져오기, ==으로 하면 문제가 발생한다
			middle=i-4000;
			needMiddle=false;
		}	
		
		if(count[i]>many) { //현재 기록된 many보다 많으면 배열을 만들어 [0]번 인덱스에 저장
			   many=count[i];
			   mode = new Integer[2];
			   
			   mode[0]=i-4000; // 4000을 더해 저장했으니 다시 빼서 가져온다
			   
		   }else if(count[i]==many && mode[1]==null) { //0번에 이미 기록되어있을 경우
			   mode[1]=i-4000; //그 다음으로 최빈값 저장
		   }
	   }
	   System.out.println(String.format("%.0f", avg));
	   System.out.println(middle);
	   System.out.println(mode[1]==null?mode[0]:mode[1]);
	   System.out.println(max-min);
}}

 

저작자표시