이진 탐색 문제풀이(feat: 개똥벌레 : 골드 )

예산

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

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

https://upload.acmicpc.net/c6fd496d-ccf5-4f9d-a06e-32b121fc6a82/-/preview/

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

https://upload.acmicpc.net/bfcbb94f-0e15-4ff9-b2ef-43e07c7ee503/-/preview/

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

나의 풀이 방향 및 코드

내가 푼 풀이

• 이진 탐생을 통한 풀이가 떠오르지 않음
• 모든 경우의 수를 탐색하는 형태로 구현

1. evenArray는 석순을, oddArray는 종유석을 필터링하여 따로 관리합니다.
2. 각 높이에 대해 석순과 종유석에 부딪히는 장애물 수를 계산합니다.
3. 모든 높이에 대해 장애물 수를 계산한 후, 그중 최소값과 해당 값을 가지는 구간의 수를 출력합니다.

문제점

: 각 높이마다 모든 장애물을 순회하면서 카운팅하는 것은 시간 복잡도가 O(N * H)로, 매우 크기 때문에 N과 H가 커지면 성능 문제가 발생할 수 있습니다.

/*
개똥벌레 문제
N : 동굴의 길이
H : 동굴 높이
array: 높이들 
*/
function solution2(N, H, array) {
  // 짝수끼리 모으기 (아래에서 위로)
  let evenArray = array.filter((item, i) => i % 2 === 0);

  // 홀수끼리 모으기 (위에서 아래로)
  let oddArray = array.filter((item, i) => i % 2 !== 0);

  // // 짝수 배열 중간 지점이 최소점일 확률이 높음
  // let evenLeft = Math.max([...evenArray]);
  // let evenRight = Math.min([...evenArray]);
  // // 홀수 배열
  // let oddLeft = Math.min([...oddArray]);
  // let oddRight = Math.max([...oddArray]);

  let arr = [];

  for (let i = 1; i <= H; i++) {
    // H 미터로 날경우
    let result = { height: 0, coll: 0 };
    result["height"] = i;
    // 짝수
    evenArray.forEach((element) => {
      if (i <= element) {
        result["coll"]++;
      }
    });

    // 홀수
    oddArray.forEach((element) => {
      if (i > H - element) {
        result["coll"]++;
      }
    });
    arr.push(result);
  }
  let arr2 = arr.map((item) => item.coll);
  console.log(arr2);

  const minColl = Math.min(...arr2);
  const minCount = arr2.filter((item) => item === minColl).length ?? 0;

  return `${minColl} ${minCount}`;
}
console.log(solution2(6, 7, [1, 5, 3, 3, 5, 1]));

---

GPT 개선 코드

설명:

1. bottom과 top 배열:
   • bottom[i]: 석순이 i 이상인 높이에서 부딪히는 석순의 개수를 누적하여 계산합니다.
   • top[i]: 종유석이 i 이상인 높이에서 부딪히는 종유석의 개수를 누적하여 계산합니다.
2. 누적합 계산:
   • bottom과 top 배열은 각각 높이가 큰 쪽부터 누적합을 구하여 각 높이에서 부딪히는 장애물의 개수를 미리 계산합니다.
3. 최소 충돌 계산:
   • 각 높이에서 석순과 종유석이 파괴되는 개수를 합산하여 최소 충돌 횟수를 구하고, 그 최소값을 가지는 구간의 개수를 카운트합니다.

성능 개선:

• 시간 복잡도: O(N + H)로, 이 방식은 주어진 입력 범위(N ≤ 200,000, H ≤ 500,000)에서도 효율적으로 동작할 수 있습니다.

이 방식은 시간 제한 내에 충분히 통과할 수 있는 효율적인 방법입니다.

function solution2(N, H, array) {
  const bottom = new Array(H + 1).fill(0); // 석순 높이 카운트
  const top = new Array(H + 1).fill(0); // 종유석 높이 카운트

  // 석순(짝수 인덱스)과 종유석(홀수 인덱스) 높이 카운트
  for (let i = 0; i < N; i++) {
    if (i % 2 === 0) {
      bottom[array[i]]++; // 석순
    } else {
      top[array[i]]++; // 종유석
    }
  }

  // 각 높이에서 부딪히는 석순과 종유석을 미리 누적합으로 계산
  for (let i = H - 1; i > 0; i--) {
    bottom[i] += bottom[i + 1]; // i 높이 이상 석순 개수
    top[i] += top[i + 1]; // i 높이 이상 종유석 개수
  }

  let minCollisions = Infinity;
  let count = 0;

  // 각 높이에서 부딪히는 장애물 수 계산
  for (let i = 1; i <= H; i++) {
    const totalCollisions = bottom[i] + top[H - i + 1]; // i 높이에서 부딪히는 총 장애물 수
    if (totalCollisions < minCollisions) {
      minCollisions = totalCollisions;
      count = 1;
    } else if (totalCollisions === minCollisions) {
      count++;
    }
  }

  return `${minCollisions} ${count}`;
}

console.log(solution2(6, 7, [1, 5, 3, 3, 5, 1]));

정리 및 마무리

• 이번에는 , 이진 탐색을주제로 문제를 풀려했지만, 방법이 떠오르지 않아서, 먼저 떠오르는 방법으로 구현하고 , 개선방안을 찾았습니다.
• 조금 어려운 문제를 가니 , 단순 이진 탐색에서 한 뎁스 더 생각해서 구현하는 방향의 문제가 생기는 것 같아, 생각을 많이 해보고 풀어야 할 것 같습니다.