[백준] 2108번_통계학(Java)

문제 풀이

백준의 2108번 문제입니다. 문제 출처

(1) 문제 파악

문제에서 알려준 그대로 연산 결과를 출력하면 되는 문제입니다.

(2) 문제 풀이 방법 생각하기

이 문제에서의 포인트는 최빈값 입니다!

숫자 값의 범위는 -4000에서 4000까지로 범위가 작으므로 각각을 인덱스로 사용하는 배열을 만들어 값의 숫자를 카운팅하였습니다.

(3) 시간 복잡도 확인

문제의 시간 제한은 2초이며 대략 2억번의 연산까지는 가능합니다.

• 처음 입력을 받아 배열에 저장하는 연산 N번
• 최빈값의 개수를 찾아내는 연산 4001 + 4001
• 최빈값 찾는 연산 N번

N의 범위는 최대 500,000이기 때문에 충분히 가능한 연산입니다.

(4) 구현

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        int mode = 0; // 최빈값

		int[] arr = new int[N];
		int[] positive_arr = new int[4001];
		int[] negative_arr = new int[4001];

		double sum = 0;

		for(int i=0; i<N; i++) {
			int temp = Integer.parseInt(br.readLine());
			
			// 평균 계산을 위한 총합 계산
			sum += temp;
			
			// 중앙값 및 범위를 위한 배열에 삽입
			arr[i] = temp;

			// 최빈값을 구하기 위함
			if(temp>=0) positive_arr[temp]++;
			else negative_arr[Math.abs(temp)]++;
        }

		// 정렬
		Arrays.sort(arr);

        int max = 0;
        for(int i=0; i<positive_arr.length; i++) {
            max = Math.max(max, positive_arr[i]);
        }
        for(int i=0; i<negative_arr.length; i++) {
            max = Math.max(max, negative_arr[i]);
        }

        List<Integer> list = new ArrayList<>();
        for(int number: arr) {
            if(number<0) {
                if(negative_arr[Math.abs(number)] == max && !(list.contains(number))) list.add(number);
            } else {
                if(positive_arr[number] == max && !(list.contains(number))) list.add(number);
            }
        }

        if(list.size() >= 2) mode = list.get(1);
        else mode = list.get(0);

        System.out.println(Math.round(sum/N));
        System.out.println(arr[N/2]);
        System.out.println(mode);
        System.out.println(arr[N-1]-arr[0]);
	}
}

(5) 결과 확인