[백준] 2108. 통계학 (자바스크립트/js/javascript/node.js)

---

내가 작성한 코드(자바스크립트)

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const N = Number(input[0]);
input.shift();
const result = [];
const array = new Array(8001);
array.fill(0);
for (let i = 0; i < N; i++) {
  let index = Number(input[i]) + 4000;
  array[index]++;
}
for (let j = 0; j < array.length; j++) {
  if (array[j] !== 0) {
    for (let k = 0; k < array[j]; k++) {
      result.push(j - 4000);
    }
  } else {
    continue;
  }
}
// 산술평균 : N개의 수들의 합을 N으로 나눈 값
function getAverage(array) {
  let sum = 0;
  for (let i = 0; i < N; i++) {
    sum += array[i];
  }
  return Math.round(sum / N);
}
// 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
function getMedian(array) {
  const mid = Math.floor(array.length / 2);
  return array[mid];
}
// 최빈값 : N개의 수들 중 가장 많이 나타나는 값
function getMostValue(array) {
  const map = new Map();
  for (let i = 0; i < N; i++) {
    if (!map.has(array[i])) {
      map.set(array[i], 1);
    } else {
      map.set(array[i], map.get(array[i]) + 1);
    }
  }
  let maxValue = 0;
  let answer = [];
  map.forEach((element, key) => {
    // forEach(값, 키, map 객체 자체)
    if (maxValue < element) {
      maxValue = element;
      answer = [];
      answer.push(key);
      // answer = key;
    } else if (maxValue === map.get(key)) {
      answer.push(key);
    }
  });
  return answer.length !== 1 ? answer[1] : answer[0];
}
// 범위 : N개의 수들 중 최댓값과 최솟값의 차이
function getRange(array) {
  return array[array.length - 1] - array[0];
}

console.log(getAverage(result));
console.log(getMedian(result));
console.log(getMostValue(result));
console.log(getRange(result));

우선 각 수의 절댓값이 4000을 넘지 않는다고 했으므로 수의 범위가 -4000 ~ 4000까지로 총 범위는 8001개 이다.

수의 범위가 많지 않기 때문에 계수정렬을 사용하면 시간을 줄일 수 있을 것이라고 판단했고

계수정렬의 경우 수의 범위가 적으면 메모리도 괜찮고 시간복잡도는 O(n)이므로 전체 수의 개수는 최대 500,000(50만)이기 때문에 시간도 충분하다고 생각했다. 

따라서 우선 주어진 입력을 계수 정렬로 정렬한 후, 우리가 구하고자 하는 산술평균, 중앙값, 최빈값, 범위를 각각 함수로 만든 후 출력하였다.

계수정렬에서  8001 크기를 가진 배열 array를 만들어서 주어진 input을 반복문으로 돌면서 array 배열의 해당하는 부분에 카운트를 해준다. (이 때 8001개인 이유는 -4000 ~ -1까지 4000개, 0이 1개, 1~4000까지 4000개이기 때문이다)

 

산술평균, 중앙값, 범위는 그냥 간단하게 구할 수 있는데, 최빈값의 경우에는 정렬이 된 배열을 돌면서 얼마나 많이 등장하는지를 세줘야 했다. 따라서 중복된 요소가 저장될 수 없으면서 키와 값을 같이 저장할 수 있는 map을 사용하여 map 안에 요소마다 몇개가 들어있는지 key와 값으로 저장을 해준다.

(1,2,3,4,4 의 경우 map안에는 {key: 1 , value: 1}, {key: 2 , value: 1}, {key: 3 , value: 1}, {key: 4 , value: 2} 이런 식으로 저장된다.)

그리고 map을 돌면서 최빈값을 구한다. 그런데 이 때 최빈값이 여러개일 수도 있으므로, 지금 타겟이 현재의 최빈값보다 크면 최빈값을 갱신하고, 최빈값을 저장하는 배열을 리셋하고 현재 값을 넣는다. 현재 타겟인 element가 현재의 최빈값이랑 같으면 최빈값을 갱신할 필요는 없이 그냥 최빈값을 저장하는 배열(answer)에 넣는다.

그렇게 반복문이 끝나면 마지막으로 answer(최빈값이 저장된 배열) 의 길이가 1이 아닌지 묻고 1이 아니라면(최빈값이 2개 이상) 두번째 값을 출력하도록 하고 배열의 길이가 1이라면 첫번째 값을 출력하도록 한다.