[ 백준 ] 2108 통계학

Link | 2108번 문제 : 통계학

Solution

빈고수를 출력하는 것이 아니면 크게 어려운 문제가 아니다.

private static void solution() throws IOException {
    int size = Integer.parseInt(reader.readLine());
    List<Integer> nums = new ArrayList<>();

    double sum = 0;
    while (size-- > 0) {
        int num = Integer.parseInt(reader.readLine());
        sum += num;
        nums.add(num);
    }
    nums.sort(Comparator.comparingInt(o -> o));

    result.append(Math.round(sum / nums.size())).append("\n")
            .append(nums.get(nums.size() / 2)).append("\n")
            .append(nums.get(nums.size() - 1) - nums.get(0));
}

하지만 이 문제에서는 최대 빈도수 수를 구하는 것 뿐만이 아니라

최대 빈도수가 동일하다면 두 번째로 작은 값을 출력해야 한다.

때문에 다음과 같이 값을 저장하는 memory와 값을 index로 하여 빈도수를 저장하는

counter list를 생성하여 해결할 수 있다.

private static void solution() throws IOException {
    int repeat = Integer.parseInt(reader.readLine());

    int sum = 0;
    List<Integer> memory = new ArrayList<>();
    List<Integer> counter = new ArrayList<>(Collections.nCopies(8001, 0));

    while (repeat-- > 0) {
        int num = Integer.parseInt(reader.readLine());
        sum += num;
        memory.add(num);
        counter.set(num + 4000, counter.get(num + 4000) + 1);
    }

    memory.sort(Comparator.comparingInt(o -> o));
    Integer max = counter.stream().max(Comparator.comparingInt(o -> o)).get();
    int most = counter.indexOf(max) - 4000;
    for (int i = counter.indexOf(max) + 1; i < counter.size(); i++) {
        Integer value = counter.get(i);
        if (value.equals(max)) {
            most = i - 4000;
            break;
        }
    }

    result.append(Math.round(sum / (double) memory.size())).append("\n")
            .append(memory.get(memory.size() / 2)).append("\n")
            .append(most).append("\n")
            .append(memory.get(memory.size() - 1) - memory.get(0));
}

-> memory를 정렬하여 중앙값과 범위를 구할 수 있다.
-> counter를 통해서 빈도수 관련 결과값을 구할 수 있다.

다만, 위의 풀이는 시간이 오래걸린다는 단점이 있다.

아래와 같이 다른 방법으로 해결하면 시간 복잡도가 좋아진다.

private static void solution() throws IOException {
    int size = Integer.parseInt(reader.readLine());
    int[] counter = new int[8001];

    double sum = 0;
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;

    for (int i = 0; i < size; i++) {
        int num = Integer.parseInt(reader.readLine());
        sum += num;
        counter[num + 4000]++;
        max = Math.max(max, num);
        min = Math.min(min, num);
    }

    int midCounter = 0, midValue = 0;
    int maxCount = 0, maxCountValue = 0;
    boolean isSecond = false;
    for (int i = min + 4000; i <= max + 4000; i++) {
        if (counter[i] <= 0) continue;

        if (midCounter < size / 2 + 1) {
            midCounter += counter[i];
            midValue = i - 4000;
        }

        if (counter[i] > maxCount) {
            maxCount = counter[i];
            maxCountValue = i - 4000;
            isSecond = true;
        } else if (counter[i] == maxCount && isSecond) {
            maxCountValue = i - 4000;
            isSecond = false;
        }
    }

    result.append(Math.round(sum / size)).append("\n")
            .append(midValue).append("\n")
            .append(maxCountValue).append("\n")
            .append(max - min).append("\n");
}

-> 평균, 범위값은 처음 값을 읽을 때 계산한다.
-> 중앙값과 빈도수 결과값은 2번째 반복문을 통해 계산한다.
-> Counter의 값이 0이 아닐 경우 개수를 세면서 중앙값을 찾는다.
-> 최대 빈도수와 2번째 값인지 확인하면서 최대 빈도수 결과값을 찾는다.