문제 개요

문제: 개똥벌레

분류: 이분 탐색, 누적 합

난이도: 골드5

문제 풀이

1. 석순과 종유석을 서로 다른 배열에 입력 받고 오름차순 정렬 한다.
2. 첫 번째 구간부터 H번째 구간까지 차례대로 이분탐색 한다.

이분탐색 시 아래의 과정을 반복한다.

(h = 구간, answer = 장애물의 최솟값, count = 그러한 구간의 수)

1. h보다 크거나 같은 석순의 개수를 구한다.
2. H-h보다 큰 종유석의 개수를 구한다.
   (종유석은 거꾸로 매달려 있으므로 h번째 구간의 장애물이 되려면 H-h보다 커야 한다.)
3. 석순과 종유석 개수의 합에 따라 answer와 count를 업데이트 한다.
   • answer보다 작다면 answer를 업데이트 하고 count를 1로 초기화 한다.
   • answer와 같다면 count를 증가시킨다.

마지막으로 answer와 count를 출력하면 정답이 된다.

예제 입력 1에 대한 풀이 과정을 그림으로 나타내면 아래와 같다.

코드

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

const [N, H] = NH.split(" ").map(Number);

const top = [];
const bottom = [];
let answer = Infinity;
let count = 0;

size.forEach((s, idx) => {
  if (idx % 2 === 0) top.push(+s);
  else bottom.push(+s);
});

top.sort((a, b) => a - b);
bottom.sort((a, b) => a - b);

// target보다 크거나 같은 수가 처음 등장하는 인덱스를 반환한다.
const lowerBound = (arr, target, start, end) => {
  while (start < end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] >= target) end = mid;
    else start = mid + 1;
  }
  return end;
};

// target보다 큰 수가 처음 등장하는 인덱스를 반환한다.
const upperBound = (arr, target, start, end) => {
  while (start < end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] > target) end = mid;
    else start = mid + 1;
  }
  return end;
};

for (let h = 1; h <= H; h++) {
  let idx;
  let temp = 0;

  idx = lowerBound(top, h, 0, N / 2);
  temp += N / 2 - idx;

  idx = upperBound(bottom, H - h, 0, N / 2);
  temp += N / 2 - idx;

  if (temp < answer) {
    answer = temp;
    count = 1;
  } else if (temp === answer) {
    count++;
  }
}

console.log(answer + " " + count);