[백준 2108번/자바] 통계학

문제

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

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

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

입력

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

출력

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

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

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

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

---

음 어렵지 않은 문제라고 생각하고 풀기 시작했는데 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다. 이 부분에서 조금 막혔다. 처음에는 최빈값을 구할 수 있는 기본적인 알고리즘(hashmap 사용)으로 풀어보았으나... 두 번째로 작은 값이 아닌 가장 작은 값이 출력되는 바람에 실패하고 새로운 마음으로 다시 풀어보았다. 아래는 HashMap으로 최빈값을 구하는 알고리즘이다.

HashMap<Integer, Integer> frequencyMap = new HashMap<>();
		for (int i = 0; i < n; i++) {
			frequencyMap.put(nums[i], frequencyMap.getOrDefault(nums[i], 0) + 1);
		}
		
		int mode = -1;
		int maxFrequency = 0;
		for (Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
			Integer num = entry.getKey();
			Integer frequency = entry.getValue();
			
			if(maxFrequency < frequency) {
				mode = num;
				maxFrequency = frequency;
			}
		}
		result.append(mode + "\n");

---

 

새로 구상한 방법.

 

// 최빈값
		int currentCnt = 1;
		int maxCnt = -1;
		int currentNum = nums[n - 1];
		int oldNum = nums[n - 1];
		for (int i = n - 1; i > 0; i--) {
			if(nums[i] == nums[i - 1]) {
				currentCnt++;
				System.out.println("currentCnt: " + currentCnt);
			} else {
				if(currentCnt >= maxCnt) {
					maxCnt = currentCnt;
					oldNum = currentNum;
					currentNum = nums[i];
					System.out.println("대체 됨!, maxCnt: " + maxCnt);
					
					// 마지막까지 대체가 된 경우 업뎃 필요
					if(i == 1 && maxCnt == 1) {
						System.out.println("마지막까지 1");
						oldNum = currentNum;
					}
				}
				currentCnt = 1;	// 값 초기화
			}
			
			System.out.printf("nums[%d]: %d, nums[%d]: %d\n", i, nums[i], i - 1, nums[i - 1]);
			System.out.printf("oldNum: %d, currentNum: %d\n", oldNum, currentNum);
			System.out.println();
		}
		result.append(oldNum + "\n");

왜 안돼...왜...왜...!

---

어디가 문제인지 찾았다. '최빈값이 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력'이라는 부분에 꽂혀서 최빈값이 하나인 경우에도 두 번째로 작은 값을 출력하게끔 코드를 짜버렸다... 다시 차분히 로직 짜보기

 

		// 최빈값
		int currentCnt = 0;
		int maxCnt = 0;
		int first = nums[n - 1];
		int second = nums[n - 1];
		for (int i = n - 1; i > 0; i--) {
			if(nums[i] == nums[i - 1]) {	// 두 값이 같을 경우
				currentCnt++;
				if(i == 1 && currentCnt > maxCnt) {
					first = second = nums[i];
				} else if(i == 1 && currentCnt == maxCnt) {
					second = first;
					first = nums[i];
				}
			} else {						// 두 값이 다를 경우
				if(currentCnt > maxCnt) {
					maxCnt = currentCnt;
					first = second = nums[i];
					System.out.printf("[cur큼]%d와 %d 비교 완료. first: %d, second: %d\n", nums[i], nums[i - 1], first, second);
				} else {
					second = first;
					first = nums[i];
					System.out.printf("[cur와max같음]%d와 %d 비교 완료. first: %d, second: %d\n", nums[i], nums[i - 1], first, second);
				}
				
				if(i == 1 && maxCnt == 0) {
					System.out.println("들어옴!");
					second = nums[i];
				}
				currentCnt = 0;
				System.out.println("현재 max: " + maxCnt);
			}
		}
		result.append(second + "\n");

와 이것도 안된다... 진짜... 하... 한 3~4퍼 가다가 틀렸다고 뜸

---

그냥 내 코드 고수하는 거 포기하고 다른 사람 코드 봄. 내가 푼 방식이랑 완전 다른데 참고하면 너무 좋을 거 같은 코드. 진짜 읽으면서 감탄했다... 해당 코드는 백준에서 2108번 정답처리가 한번 된 후에야 볼 수 있다.
https://www.acmicpc.net/source/63890671

해당 코드를 90퍼센트 이상 이해한 후에 동일한 로직으로 직접 짜봤다. 사실 정답인 코드를 몇 번이나 봤음에도 직접 써보니깐 잘못된 결과가 몇번이나 나왔지만... 그래도 끝까지 로그를 찍어보면서 결국 해냈다. 

3일간 잡고 있던 나 칭찬해...

 정답 코드!

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

public class BJ2108_2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[8001];	// 배열에는 각 숫자(인덱스)의 빈도를 저장
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		int sum = 0;
		
		for (int i = 0; i < N; i++) {
			
			int input = Integer.parseInt(br.readLine());
			nums[input + 4000]++;
			
			if(input > max) {
				max = input;
			}
			
			if(input < min) {
				min = input;
			}
			
			sum += input;
		}
		
		// 2. 계산: 산술평균, 중앙값, 최빈값, 범위
		int cnt = 0;
		int mid = min;
		int mode = min;
		int maxFreq = 0;
		Boolean first = false;
		
		for (int i = min + 4000; i <= max + 4000; i++) {
			if(nums[i] > 0) {
				
				// 중앙값
				if(cnt <= N / 2) {
					cnt += nums[i];
					mid = i - 4000;
				}
				
				// 최빈값
				if(nums[i] > maxFreq) {
					mode = i - 4000;
					first = true;
					maxFreq = nums[i];
				} else if(nums[i] == maxFreq && first) {
					mode = i - 4000;
					first = false;
				}
			}
		}
		
		int avg = (int)Math.round((double)sum / N);	// 산술평균
		int range = max - min;	// 범위
		
		System.out.println(avg + "\n" + mid + "\n" + mode + "\n" + range);
		
	}
}