중앙값 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/120811

프로그래머스

 

들어가기 전 생각

중학교 3학년 때 배우는 중앙값 문제다. 후에 써놨지만 나는 제한사항 1번인 "array의 길이는 홀수입니다." 라는 조건을 못 보고 풀었다. 중앙값이란 대푯값 중 하나인데, N개의 값을 크기 순으로 늘어놓았을 때 가장 가운데에 있는 값이다. N이 홀수일 때는 중앙에 있는 값을, 짝수일 때는 중앙에 있는 값 두개의 평균으로 한다. 극단적인 값이 있는 경우, 평균값보다 중앙값이 더 유용하다.

여기서 N이 홀수냐, 짝수냐에 따라 해야할 일이 달라지는데, 우선 배열을 정렬한 후, 홀수냐 짝수냐에 따라 코드를 작성하면 될 것 같다는 생각을 하고 풀기 시작했다. 

 

 

정렬

자바스크립트로 정렬은 써 본 적이 없다. 그래서 정렬하는 문법을 찾아보니 배열.sort()로 하는 것을 봤다. 그런데, 유니코드 순서에 따라서 오름차순 정렬이라고 한다. 즉 [1,10,2] 이런 식으로 정렬이 된다는 것이다. 

그래서, 요소 두 개를 비교할 때, 요소 a,b에 대하여 a-b의 결과가 양수라면 a가 크니까 뒤로, 음수라면 b가 크니까 앞으로 하는 함수를 만들어 줘야 한다. 

[10, 2, 1].sort()       // -> [1, 10, 2]  
[10, 2, 1].sort((a,b)=>a-b) // -> [1, 2, 10]

물론 내림차순을 할 경우에는 b-a로 하면 된다. 

그러면 여기서  => 이 다음에 함수를 적는데, 여기에 내가 원하는대로 임의의 순서로 짤 수 있지 않을까? 생각이 들었다.

 

다음은 홀수 먼저, 짝수가 나중에 나오는 정렬을 구현해 본 것이다.

let nums = [5, 2, 9, 8, 3, 4];

nums.sort((a, b) => {
  let modA = a % 2, modB = b % 2;
  if (modA !== modB) return modA - modB; // 홀수가 먼저
  return a - b; // 같은 그룹 내에서는 오름차순
});

console.log(nums); // [3, 5, 9, 2, 4, 8]

홀짝은 2로 나눴을 때 나머지로 판별하는데, 요소 a와 b를 2로 나누어 각각 modA, modB 에 홀수면 1 짝수면 0이 되게끔 한다.

이 때, if문 조건을 보면 나머지a와 b가 다를 때, 즉 홀수와 짝수가 분명하게 나눠지게 된다면 홀수가 먼저 나오게끔 한다.

짝수가 먼저 나오게끔 하려면  modA, modB의 순서를 바꾸면 된다.

 

다음은 랜덤 정렬이다. ( 물론 이것이 진짜 무작위가 아니고 완전 균등 분포가 나오지 않으며 fisher-yates 알고리즘을 쓰지 않았음).

 

let arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);
console.log(arr);

Math.random()은 0이상 1미만의 무작위 소수인데 그 사이인 0.5를 빼 무작위로 만든다 

만약 0.5가 아닌 다른 숫자들이라면?? 감이 잘 잡히지 않아 직접 실험을 해 봤다. 아마 느낌상 숫자에 따라 덜 섞일 것 같은데

이 "덜 섞인다"의 의미를 파악해야 한다. 자기 자리에 그대로 있을 확률을 말하는 것 같다. 그러므로 숫자가 0.5보다 작아지면 뒤로 보낼 확률이 커지고, 커지면 앞으로 보내질 확률이 커질 것이다. 

다음은 내가 작성해 실험해 본 코드다. 

function testShuffle(c, trials = 100000) {
  let countFront = 0;
  let countBack = 0;

  for (let i = 0; i < trials; i++) {
    let result = Math.random() - c;
    if (result < 0) countFront++;
    else countBack++;
  }

  console.log(`c = ${c}`);
  console.log(
    `앞으로 보내는 확률: ${((countFront / trials) * 100).toFixed(2)}%`//toFixed는 반올림
  );
  console.log(`뒤로 보내는 확률: ${((countBack / trials) * 100).toFixed(2)}%`);
  console.log("-----");
}

// 여러 기준값으로 비교
testShuffle(0); // 항상 뒤로
testShuffle(0.2); // 20:80
testShuffle(0.5); // 50:50 (진짜 랜덤 비슷)
testShuffle(0.8); // 80:20
testShuffle(1); // 항상 앞으로

확인 결과

 

생각 했던 대로 숫자가 작을수록 뒤로, 커질수록 앞으로 나옴을 확인 해 볼 수 있었다.

 

중앙값

그렇다면 정렬은 처리 해서 내가 원하는 대로 오름차순 정렬(중앙 값 같은 경우는 내림차순 정렬을 해도 문제가 없긴 하다)을 했으니, 이제 중앙값을 찾아야한다

 

요소의 개수가 홀수냐 , 짝수냐로 나뉘기 때문에 array.length를 통해 길이로 판단할 것이다.

홀수일경우, 예를들어 5개라고 생각 해보자. 그렇다면 3번째 있는 값이 중앙값이다. (인덱스로는 2)

그러므로 (array.length - 1 )/2 로 인덱스가 2가 추출 될 수 있도록 한다.

짝수일경우, 예를들어 6개라고 생각 해보자. 그렇다면 3,4번째 있는 값의 평균이 그 중앙값이 된다. (인덱스로는 2,3)

그러므로, (array[array.length / 2 - 1] + array[array.length / 2]) / 2 로 인덱스가 2,3이 추출 될 수 있도록 한다.

 

function solution(array) {
  var answer = 0;
  array.sort(function (a, b) {
    return a - b;
  });
  if (array.length % 2 == 0) {
    //짝수일경우
    answer = (array[array.length / 2 - 1] + array[array.length / 2]) / 2;
  } else {
    // 홀수일 경우
    answer = array[ (array.length - 1) / 2 ];
  }
  return answer;
}

 

마치며

사실 array의 길이가 홀수라는 사실을 모른 채 진행을 했으나 문제 풀이 시간이 더 걸리거나 하진 않았다. 결국 배열과 인덱스 그리고 정렬을 사용하는게 주였기 때문이다. 가장 크게 얻어간 내용은 자바스크립트만의 특이한 sort방식이였다. 아무것도 해놓지 않으면 유니코드대로 정렬을 하니 반드시 내부에 임의의 함수를 써야 내가 원하는 대로 작동하겠구나 라는 사실을 느꼈다.