[정렬] 백준 - 통계학

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

2108번: 통계학

 

 

-문제해설

반례를 못찾다가 질문검색 10페이지까지 가면서 하나 찾아서 간신히 풀었다...ㅠ

 

그리고 이 글을 참고하면 좋을 것 같다.

https://www.acmicpc.net/board/view/40713

 

 

먼저 배열로 받은 다음 Arrays.sort를 사용할 수 있겠지만 왠지 시간이 오래 걸릴 것 같아서 입력값을 arr배열의 인덱스로 넣고 최빈값을 구하기 위해 arr[인덱스] +=1 을 해주었다. 이때 -4000~4000범위이니깐 배열의 크기는 8001이고

4000부터 시작되도록하였다.

 

예를 들어 입력값이 10일 경우에 arr[4010] = 1 이 되고 

-10일 경우에 arr[3890] = 1이 된다.

또 -10일 경우에 arr[3890] = 2가 된다.

이렇게 해서 인덱스의 값인 1, 2는 최빈값을 구할 때 사용할 수 있다.

 

또한 입력받으면서 동시에 산술평균을 구하기 위한 전체 입력값의 합을 구했고 소수점 첫 번째 자리 반올림이므로

(int)Math.round( (sum/(double)n) ) 를 이용하였다. 

 

또한 입력받으면서 max와 min값을 구해서 바로 값의 범위를 구했다.

int min = Integer.MAX_VALUE; 
int max = Integer.MIN_VALUE;

이렇게 지정해놓고

입력값 < min ---> min = 입력값

입력값 > max ---> max = 입력값

 

범위 = max - min을 이용한다.

 

중앙값은 arr배열을 순회하면서 arr[i] >= 1이면 arr[i] 가 0이 될 때까지 crr이란 ArrayList에 인덱스값을 저장했고

반복문을 빠져나온 다음에 mid = crr.get( crr.size()/2 ); 를 이용해서 구했다.

 

 

최빈값 구하는게 가장 어려웠는데 brr이란 최빈값이 저장될 ArrayList를 선언해주고 tmp=1라는 빈도수 저장 변수를 선언한다.

그리고 arr배열을 순회하면서

arr[i] == tmp 이면 brr.add( i-4000 ) 으로 brr리스트에 인덱스값을 저장하고

arr[i] > tmp 이면 기존 빈도수보다 더 큰 빈도수가 등장한 것이므로 brr리스트를 재선언하고 brr.add( i-4000 )을 한다.

 

그리고 반복문을 빠져나온뒤에 brr.size() > 1이면 두 번째 값을 mode에 저장하고

brr.size() > 1이 아니면 그냥 첫 번째 값을 mode에 저장한다.

 

말로 설명이 어려우니 코드의 주석과 함께 보길 바란다. ㅎ

 

 

여태까지 사용했던 반례를 같이 추가한다.

반례1
7
2
2
5
5
4
5
5
정답
4
5
5
3


반례2
5
-3
-3
-2
1
0
정답
-1
-2
-3
4

반례3
11
-446
-3855
-2693
-3819
-1071
-2994
-1562
-3147
-1008
-446
-2849
정답
-2172
-2693
-446
3409

반례4
5
-4000
-4000
5
5
1
정답
-1598
1
5
4005

반례5
5
-1
-1
-1
0
0
정답
-1
-1
-1
1

반례6
11
1
1
1
2
2
2
3
3
3
4
4
정답
2
2
2
3

 

 

-자바

package sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class BJ2108 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		int[] arr = new int[8001];		//입력값이 arr 인덱스가 된다.
		int sum = 0;					//산술평균에 쓰일 전체합
		int min = Integer.MAX_VALUE;	//범위 구할 때 쓰일 min
		int max = Integer.MIN_VALUE;	//범위 구할 때 쓰일 max
		
		int mean = 0;		//산술평균
		int mid = 0;		//중앙값
		int mode = 0;		//최빈값
		int range = 0;		//값의 범위
		
		for( int i=0; i<n; i++ ) {
			int tmp = Integer.parseInt( br.readLine() );
			
			//최소값과 최대값을 구한다.
			if( tmp < min ) min = tmp;	
			if( tmp > max ) max = tmp;
			
			sum += tmp;	//산술평균 구하기위해 전체 입력값들 더하기
			arr[4000+tmp]++;	//최빈값 구할 때 사용하기위해 해당 인덱스의 값을 1씩 증가
		}

		ArrayList<Integer> brr = new ArrayList<Integer>();	//최빈값 저장될 리스트
		ArrayList<Integer> crr = new ArrayList<Integer>();	//중앙값 구하기 위해 새로운 배열을 만든다.
		
		int tmp = 1;	//가장 큰 빈도수가 저장될 임시변수
		int k = 0;		//crr배열 인덱스를 위한 변수
		
		for( int i=4000+min; i<=4000+max; i++ ) {
			
			//빈도수가 1 이상일 때
			if( arr[i] >= 1 ) {
				
				//중앙값 구하기위해 crr배열에 값을 넣는다.
				int a = arr[i];
				while( a --> 0 ) { crr.add(i-4000); }
				
				//기존빈도수보다 큰 빈도수가 나타났을 때 
				//최빈값 빈도수 변수 초기화,
				//최빈값 저장될 리스트 초기화하고 다시 저장
				if( arr[i] > tmp ) {
					brr = new ArrayList<Integer>();
					tmp = arr[i];				
					brr.add( i-4000 );
					
				//기존 빈도수와 같은 빈도수일 때 최빈값 리스트에 값 저장
				} else if( arr[i] == tmp ) {
					brr.add( i-4000 );
				}
				
				k++;
			}
		}
		
		//산술평균 구하기
		mean = (int)Math.round( (sum/(double)n) );
		
		//중앙값 구하기
		mid = crr.get( crr.size()/2 );
		
		//최빈값 구하기
		//최빈값 리스트가 1보다 클 경우 두 번째로 큰 값이 최빈값이다.
		if( brr.size() > 1 ) mode = brr.get(1);
		//최빈값리스트 크기가 1일 경우 가장 큰 최빈값 하나밖에 없다.
		else mode = brr.get(0);	

		//값의 범위 구하기
		range = max-min;
		
		StringBuffer sb = new StringBuffer();
		sb.append( mean+"\n" + mid+"\n" + mode+"\n" + range+"\n" );
		System.out.println( sb );
	}
}

 

-파이썬

import sys

readline = sys.stdin.readline
n = int( readline() )

Mean = 0
Mid = 0
Mode = 0
Range = 0

arr = [ 0 for _ in range( 8001 ) ]
Max = -5000; Min = 5000;
Sum = 0


for _ in range( n ):
    tmp = int( readline() )
    if tmp < Min: Min = tmp
    if tmp > Max: Max = tmp
    Sum += tmp

    arr[ 4000+tmp ] += 1

brr = []; crr = []
tmp = 1
for i in range( 4000+Min, 4000+Max+1 ):

    if arr[i] >= 1:
        for _ in range( arr[i] ): 
            crr.append( i-4000 )

        if arr[i] > tmp:
            brr = []
            tmp = arr[i]
            brr.append( i-4000 )

        elif arr[i] == tmp:
            brr.append( i-4000 )

Mean = round( Sum/n )

Mid = crr[ len(crr)//2 ]
if len(brr) > 1: Mode = brr[1]
else: Mode = brr[0]
Range = Max - Min

s = str(Mean)+"\n"+str(Mid)+"\n"+str(Mode)+"\n"+str(Range)+"\n"
sys.stdout.write( s )