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

메모리초과 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const N = input[0];

let arr = [];
for (let i = 0; i < N; i++) {
  arr.push(Number(input[i + 1]));
  // 오름차순 정렬 후 mid값 출력, 짝수 개라면 가운데 중 작은 수
  arr.sort((a, b) => a - b);
  // 길이가 4면 index (4-1)/2 = 1.5 -> 내림해서 1
  let mid_idx = Math.floor((arr.length - 1) / 2);
  let mid_num = arr[mid_idx];
  console.log(mid_num);
}

초기 아이디어

for문으로 배열에 새로 값이 추가될 때마다 정렬 후, 가운데 값을 리턴

→ 메모리 초과

삽입정렬

매번 sort()를 하는 대신, 정렬된 위치에 '삽입'만 합니다 (Insertion Sort 개념)

이진 탐색을 이용해 삽입 위치를 찾으면 더 빠릅니다.

최종코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const N = Number(input[0]);
let result = "";
let arr = [];

for (let i = 0; i < N; i++) {
  const num = Number(input[i + 1]);
  // 매번 정렬하는 대신 정렬된 위치에 삽입하기
  // 이진탐색을 이용해 삽입 위치를 찾기
  let low = 0;
  let high = arr.length;

  while (low < high) {
    let mid = Math.floor((low + high) / 2);
    // 배열에 넣어야할 값이 arr[mid]값보다 크다면
    // low의 인덱스를 mid+1로 설정
    // 배열에 넣어야할 값이 arr[mid]값보다 작다면
    // high의 인덱스를 mid로 설정
    if (arr[mid] < num) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  // 계속 좁혀가면서 적절한 인덱스 위치를 찾음
  // low의 인덱스 위치에 추가
  arr.splice(low, 0, num);
  
  let mid_idx = Math.floor((arr.length - 1) / 2);
  result += arr[mid_idx] + "\n";
}

console.log(result);

arr.splice(low, 0, num);

splice(시작_인덱스, 삭제할_개수, 추가할_요소) 순서

• low: 이진 탐색으로 찾아낸 숫자가 들어갈 최적의 위치(인덱스)입니다.
• 0: "아무것도 지우지 마라"는 뜻입니다. 기존 데이터를 삭제하지 않고 삽입만 하겠다는 핵심 설정입니다.
• num: 배열에 새롭게 추가할 데이터 값입니다.