문제 링크 - 백준 : 배

문제 설명 및 접근

항구에 크레인이 N대 있고, 옮겨야 할 박스가 M개 있다. 각 크레인은 무게 제한이 있어서 자신보다 무거운 박스는 옮길 수 없다. 모든 크레인은 동시에 움직이며, 박스를 옮기는 데 1분이 걸린다.

모든 박스를 옮기는 데 걸리는 최소 시간을 구해야 한다.

1. 첫 번째 접근 (시간 초과)

직관적으로 그리디(Greedy) 방식이 떠올랐다.

  1. 크레인과 박스를 모두 내림차순으로 정렬한다.
  2. 무거운 박스는 힘센 크레인이 처리해야 효율적이다.
  3. isMoved라는 방문 체크 배열을 만들어서, 옮긴 박스는 true로 표시하고 넘어간다.

하지만 이 방식은 시간 초과가 발생했다.

시간 초과 코드

function solution(N, cranes, M, goods) {
  // 기타 코드들..
  const isMoved = new Array(M).fill(false);

  while (curGood < M) {
    curTime++;
    for (const crane of cranes) {
      // 매번 처음부터 끝까지 순회하며 안 옮겨진 박스를 찾음
      for (let i = 0; i < M; i++) {
        if (isMoved[i] || goods[i] > crane) {
          continue;
        }
        isMoved[i] = true;
        curGood++;
        break;
      }
    }
  }
  return curTime;
}

왜 실패했을까?

이 로직은 시간이 지날 때 마다 for 문을 통해 모든 박스(M)을 다시 순회한다.

박스가 이미 옮겨졌더라도, isMoved를 확인해야 하므로 루프를 돈다. => 박스가 10000개라면… 계속해서 루프에 포함되므로 O(M^2)에 가까워진다.

아이고.

따라서 조금 과감한 선택을 해 보았다.

“배열에서 아예 제거해버리자”

배열에서 물리적으로 제거.

방문 처리 대신, 옮긴 박스를 배열에서 아예 splice 해보았다.

splice 자체도 저렴하지 않을 것 같아서 조금은 도전적인게 아닌가 했지만 잘 생각해보자.

생각해보면 M이 커질수록, M이 작아진다! (순회 이후에 말하는 것)

따라서 누적되는 M개의 반복 vs 작아지는 M개

다소 의역 : 깃발 꽂기 vs 바로 가져다 버리기

정도로 요약된다.

정답

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split("\n");

const N = parseInt(input[0].trim());
const cranes = input[1]
  .trim()
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a);

const M = parseInt(input[2].trim());
const goods = input[3]
  .trim()
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a);

const ans = solution(N, cranes, M, goods);
console.log(ans);

/**
 * ## 백준 골드 1092 : 배
 *
 * ### [문제 링크](https://www.acmicpc.net/problem/1092)
 *
 * @param {number} N 크레인의 수
 * @param {number[]} cranes 각 크레인의 무게 배열
 * @param {number} M 화물의 수
 * @param {number[]} goods 각 화물의 무게 배열
 * @returns number
 */
function solution(N, cranes, M, goods) {
  const maxGoodW = goods[0];
  const maxCraneW = cranes[0];

  // 가장 무거운 짐을 가장 힘센 크레인이 못 들면 영원히 못 옮김
  if (maxCraneW < maxGoodW) {
    return -1;
  }

  let curTime = 0;

  // 화물이 모두 사라질 때까지 반복
  while (goods.length > 0) {
    let craneIdx = 0;
    let goodIdx = 0;

    curTime++;

    // 이번 턴에 사용할 수 있는 크레인과 남은 화물을 비교
    while (craneIdx < N && goodIdx < goods.length) {
      // 현재 크레인이 현재 화물을 들 수 있다면
      if (cranes[craneIdx] >= goods[goodIdx]) {
        // 화물을 실어 보냄 (배열에서 삭제)
        goods.splice(goodIdx, 1);
        // 크레인 사용 완료, 다음 크레인으로
        craneIdx++;
      } else {
        // 못 들면, 더 가벼운 다음 화물을 확인
        goodIdx++;
      }
    }
  }

  return curTime;
}

핵심 로직 1 goods.splice(goodIdx, 1) : 화물을 옮겼다면, 배열에서 삭제한다.

핵심 로직 2 else { goodIdx++} : 현재 크레인이 들 수 없다면, 조금 더 가벼운 물건으로 (최소한의 시간을 위해) 인덱스를 넘긴다.

마무리하며

논리적 처리가 항상 정답은 아니다.

코딩(물리)가 성능상 유리할 수 있음을 배울 수 있는 좋은 문제였다.

더 열심히 하자. 포기하지 않음 된다.

화이팅화이팅

-뱅-