[Baekjoon] #2548 대표 자연수 (Node.js)

📝 문제

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

👻 풀이

아이디어

처음엔 브루트포스 알고리즘을 이용해 하나씩 값을 찾아보는 방법으로 문제를 해결했다. 하지만 2,404ms 만큼의 시간을 소모했기 때문에 더 좋은 방법이 없을까 고민했다.

고민해본 결과 이 문제는 단순히 중간값을 구하기만 하면 되는 문제였다.. 이 경우 시간복잡도를 180ms까지 줄일 수 있었다.

알고리즘

배열을 정렬한 뒤 홀수일 경우 중간 값을, 짝수일 경우 중간값 중 작은 것을 반환한다.

💻 소스코드

const fs = require('/dev/stdin');
let [cnt, arr] = fs.readFileSync('input.txt').toString().split('\n');
arr = arr
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);

console.log(arr[~~((cnt - 1) / 2)]);