Baekjoon 문제 풀기 (2108번 : 통계학) Java

2108번 : 통계학

1. 문제읽기

---

3번 최빈값이 복병이다..!

파이썬으로 풀었던 문제를 순서대로 자바로 풀고 있는데, 확실히 자바가 더 까다롭다는 말을 이해할 것 같다…
파이썬으로는 쉽게 풀 수 있는 걸 자바에서는 좀 돌아가야 하는 느낌이랄까..ㅠ
언어는 도구라고 하지만 왜 사람들이 파이썬으로 코테를 추천하는지 알 것 같다..

2. 제출 코드

---

역시나 1, 2, 4번은 쉬웠지만 복병은 3번 최빈값이였다.
map, LinkedList를 사용해서 이것저것 시도하여 풀어봤지만 정렬에 정렬을 또 해야하는 상황이 생겨 아니겠구나.. 하고 포기했다.
아래는 내가 풀려고 시도해본 코드. 실패이다.

1, 2, 4번은 쉬우므로 패스하고, 3번을 HashMap으로 count해서 넣어준 뒤에, value값을 정렬해서 뒤에서 첫번째, 두번째 값이 같을 경우 뒤에서 두번째 값을 출력했다.
여기서 간과한 사실은 예제 1번같은 경우 모든 숫자가 1번씩만 나오므로 1,1 / -2,1 / 2,1 / 3, 1 / 8, 1 이렇게 나열되고 결국 답인 1이 아닌 3을 출력해버린다.
이것을 해결하려면 같은 value값에서 key값을 또 정렬해줘야하는데 아니다 싶어서 포기했다.
심지어 예제 3번은 IndexOutOfBound가 나온다. map의 length로 값을 구하는게 아닌 n-1, n-2로 값을 구해서 그런 것으로 보인다.

또한 0.5를 더하는 것으로 반올림을 해줬는데, 이렇게 하면 음수값에서 제대로 답이 나오지 않으므로 그냥 Math.round로 반올림하여 해결하는 것이 좋겠다.

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

public class BOJ2108 {
    public static void main(String[] args) throws IOException {
        // -1, -2, -3, -1, -2
        // 산술평균 : 전부 더해서 n으로 나누기, 정수로 나타냄
        // 중앙값 : sort해서 length/2하고 값 출력
        // 최빈값 : hashmap으로 정리, 최빈값의 value가 2개면 두번째로 작은 값 출력
        // 범위 : 최댓값 - 최솟값

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }
        StringBuilder sb = new StringBuilder();
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        sb.append((int)((sum/(double)n)+0.5)).append("\n");
        int[] arrC = arr.clone();
        Arrays.sort(arrC);
        sb.append(arrC[n/2]).append("\n");

        Map<Integer,Integer> map = new HashMap<>();
        for(int i : arr) {
            if(map.get(i) == null) { // map에 값이 없다면
                map.put(i,1);
            } else {
                int bkVal = map.get(i);
                map.remove(i);
                map.put(i,bkVal+1);
            }
        }
        List<Map.Entry<Integer,Integer>> entryList = new LinkedList<>(map.entrySet());
        entryList.sort(Map.Entry.comparingByValue());
        if(n > 1 && (entryList.get(n-1).getValue() == entryList.get(n-2).getValue())) {
            sb.append(entryList.get(n-2).getKey()).append("\n");
        } else if(n > 1 && (entryList.get(n-1).getValue() != entryList.get(n-2).getValue())) {
            sb.append(entryList.get(n-1).getKey()).append("\n");
        }


        sb.append(arrC[n-1]-arrC[0]);
        System.out.println(sb);

    }
}

3. 공부할 것

---

Arrays.sort는 O(NlogN)의 시간복잡도를 가지므로 카운팅 정렬 O(N)으로 푸는 것이 좋다.
카운팅 정렬은 알고리즘에 자주 나오는 것 같으니 이번 기회에 잘 정리해둬야겠다.
(파이썬 count 방법이 그립네..)

Counting Sort (카운팅 정렬 / 계수 정렬)

• 카운트 해야하는 범위의 수를 index로 가지는 배열을 생성한다.
• 순회하며 각 값이 나올 때마다 해당 값을 index로 하는 새로운 배열의 값을 1 증가시킨다.
• 즉 새로운 배열을 counting 이라고 했을 때, counting[7] = 2 의 뜻은 7이 2번 카운트 되었다는 뜻.
• 입력되는 수의 개수는 적지만, 수의 범위가 클 경우 메모리 낭비가 심하다는 것이 단점

정답 코드

카운팅 정렬로 푼 코드들을 참고해가며 이해하려고 노력했는데 이해가 잘 안간다..
다음에 다시 풀어보는 것으로 하고 조금 더 쉽게 접근했던 코드가 있어 참고하며 해결했다.

1번은 +0.5부분을 Math.round로 해결하였고, 2번과 4번은 푼 코드 그대로 두었다.
3번 최빈값을 구하는 부분은 배열에 카운팅을 해준 뒤, 배열을 순회하면서 max값을 찾아준 다음 또 한번 배열을 순회한 후 arrayList에 넣어서 size가 1이면 그대로 출력, 1이 아니면 sort하여 2번째 값을 출력하는 방법이다.
카운팅 정렬을 사용한 코드보다는 느리지만 그래도 이해할 수 있는 로직으로 짜여있어 풀기 쉬웠다.

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

public class BOJ2108 {
    public static void main(String[] args) throws IOException {
        // -1, -2, -3, -1, -2
        // 산술평균 : 전부 더해서 n으로 나누기, 정수로 나타냄
        // 중앙값 : sort해서 length/2하고 값 출력
        // 최빈값 : list에 max값
        // 범위 : 최댓값 - 최솟값

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }
        StringBuilder sb = new StringBuilder();
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        sb.append((int)(Math.round(sum/(double)n))).append("\n");
        int[] arrC = arr.clone();
        Arrays.sort(arrC);
        sb.append(arrC[n/2]).append("\n");

        int max = Integer.MIN_VALUE;
        int[] arrP = new int[8001]; // -4000 ~ 0 ~ 4000
        List<Integer> maxArr = new ArrayList<>();
        for(int i = 0; i < n; i++) {  // arrP에 카운트하기
            arrP[arr[i]+4000]++;  // 4000을 0으로 두고 시작
        }
        for(int i = 0; i <= 8000; i++) {  // 카운트배열에서 max 찾기
            if(max < arrP[i]) {
                max = arrP[i];
            }
        }
        for(int i = 0; i <= 8000; i++) {  
            if(max == arrP[i]) {  // max값이 카운트 배열의 값과 같다면
                maxArr.add(i-4000);  // maxArr에 최빈값 저장
            }
        }
        if(maxArr.size() == 1) {  // 최빈값이 1개라면
            sb.append(maxArr.get(0)).append("\n");  // 그대로 출력
        } else {  // 최빈값이 2개 이상이라면
            Collections.sort(maxArr);  // 오름차순으로 정리 후
            sb.append(maxArr.get(1)).append("\n");  // 두번째 값 출력
        }
        sb.append(arrC[n-1]-arrC[0]);
        System.out.println(sb);

    }
}