백준 2108번 통계학 자바 Java / 백준 단계별로 풀어보기 9단계 / 9. 정렬

백준 9단계 5번 문제 - 2108 통계학

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

2108번: 통계학

 

 

 

---

9. 정렬 (5) 백준 2108번 문제 통계학

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

중앙값, 최빈값, 범위는 카운팅 정렬을 이용했을 때 나타낼 수 있다

우선 카운팅 정렬로 입력된 수들을 정렬한다

 

1. 첫째 줄 산술평균: 모두 더한 후 n으로 나눈다

2. 둘째 줄 중앙값: 오름차순으로 나열한 후 (2/n)+1(n은 정수라서 버려지는 값) +1(인덱스니까)에 위치한 숫자를 출력

3. 셋째 줄 최빈값: count[입력값]이 가장 큰 수를 출력한다 (두번째로 작은 값은 모르겠다)

4. 넷째 줄 범위: count[n-1] (최대값) - count[0] (최소값)

 

→이것들은 count의 인덱스값에 음수가 들어갈 수 없으므로 불가능하다

 

 

 

---

오답

---

 

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int arr[] = new int[n];
        int count[] = new int[4001];
        int sum = 0;
        int newarr[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            sum += arr[i];
        }
        
        System.out.println(sum/n);    //평균
        
        //카운팅정렬 시작
        for(int i = 0; i <= n; i++) {
            count[arr[i]]++;
        }
        
        for(int i = 0; i < count.length; i++) {
            while(count[i] > 0) {
                newarr[i] = i;
                count[i]--;
            }
        }
        System.out.println(newarr[(n/2)+1]); //중앙값
        System.out.println(newarr[newarr.length-1] - newarr[0]); //범위
    }
}

 

여기까지 짜봤다가 실행해보니 23번째 줄에서 -2는 인덱스값의 범위를 넘는다는 에러가 떠서

카운팅 정렬을 이용하는 건 불가능하다는 걸 알았다

 

 

 

---

정답 인정 코드

---

 

https://st-lab.tistory.com/108

이 블로그를 참고했다

https://www.youtube.com/watch?v=XBA3SPTyOWA 이 영상에서 알고리즘 순서별로 참고했다

음수가 들어가서 카운팅 정렬을 못 쓴다고 생각했는데, -4000 ~ 4000 까지 범위이므로 +4000을 해줘서 사용할 수 있게 만든다

 

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int countarr[] = new int[8001];
        
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int median = 4001; //중앙값. -4000~4000 제외
        int mode = 4001; //최빈값. -4000~4000 제외
        
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            countarr[x+4000]++;
            
            sum += x;
            max = Math.max(max, x);
            min = Math.min(min, x);
        }
        
        int count = 0;
        int mode_max = 0;
        boolean flag = false;
        
        for(int i = min + 4000; i <= max + 4000; i++) {
            
            if(countarr[i] > 0) {    //입력된 값이 있다면
                if(count < (n+1)/2) {    //누적횟수가 전체 길이의 절반보다 작은
                    count += countarr[i];    //값이 몇 번씩 입력됐는지
                    median = i - 4000;
                }
                
                if(mode_max < countarr[i]) {
                    mode_max = countarr[i];
                    mode = i - 4000;
                    flag = true;
                }else if(mode_max == countarr[i] && flag == true) {
                    mode = i - 4000;
                    flag = false; //같은 최빈값 나와도 두번째(최초로 else if문 조건을 만족한)에서 멈추기 위함
                }
            }
        }
        System.out.println(Math.round((double)sum/n));
        System.out.println(median);
        System.out.println(mode);
        System.out.println(max - min);
    }
}

 

 

 

 

---

직후 백지 복습

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Day29_B_2108_2 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int countarr[] = new int[8001];
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int median = 4001;
        int mode = 4001;
        
        for(int i = 0; i < n; i++) {
            int x = Integer.parseInt(br.readLine());
            countarr[x+4000]++;
            sum += x;
            max = Math.max(max, x);
            min = Math.min(min, x);
        }
        
        int count = 0;
        int mode_max = 0;
        boolean flag = false;
        
        for(int i = min + 4000; i <= max + 4000; i++) {
            if(countarr[i] > 0) {
                if(count < ★(n+1)/2★) {
                    count += countarr[i];
                    median = i - 4000;
                }
                
                if(mode_max < ★countarr[i]★) {　　　　　　　　　　★mode_max = countarr[i];★                   mode = i - 4000;
                    flag = true;
                }else if(★mode_max == countarr[i]★ && flag == true) {
                    mode = i - 4000;
                    flag = false;
                }
            }
        }
        System.out.println(Math.round((double)sum/n));
        System.out.println(median);
        System.out.println(mode);
        System.out.println(max - min);
    }
}

 

★로 표시한 부분은 틀렸거나 못 적은 부분

BufferedReader로 적었다

 

 

 

---

사실 어제도 도전했는데 이해가 가지 않아서 오늘 다시 본 문제다

지금까지 문제 중 가장 어려웠던 문제는 아니지만 왠지 모르게 구글링해서 나온 답변들(여러 개 봤지만 결국 맨 처음 뜨는 블로그를 기반으로 정답 코드를 작성했다)도 잘 와닿지 않았다

해야 할 일이 있어 시간적 여유가 없었다는 이유도 있다...

뭐.. 이것들은 다 변명이고

 

어쨌든~ 그렇다! 단계가 올라갈수록 시간적 여유를 두고 도전해야 할 것 같다

이 문제는 하루에 한 번씩 백지 복습 할 예정