백준 / 구현 / 18111번 / 마인크래프트 / JS

문제 간단설명

N×M 크기의 땅을 모두 동일한 높이로 만드는데 필요한 최소 시간을 구하고, 그때의 땅의 높이를 출력하면 된다.

만약 최소 시간으로 가능한 경우가 여러가지 일 경우, 가장 높은 높이를 출력하면 된다.

 

조건:

1. (i, j) 위치의 블록을 제거해 인벤토리에 넣는 작업: 2초 소요
2. 인벤토리에서 블록을 꺼내 (i, j) 위치에 쌓는 작업: 1초 소요
3. 초기 인벤토리에 B개의 블록이 주어진다.
4. 높이는 0~256 사이여야 한다.

 

제한 사항

• 1 <= M(가로), N(세로) <= 500
• 0 <= B(시작할 때 들어있는 블록의 개수) <= 6.4 * 10^7

실패 코드 (시간 초과)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

const [N, M, B] = input.shift().split(' ');
const map = input.map((row) => row.split(' ').map(Number));

function solution() {
  const min = Math.min(...map.flat());
  const max = Math.max(...map.flat());

  let minTime = Infinity;
  let maxHeight = -Infinity;

  for (let targetHeight = min; targetHeight <= max; targetHeight++) {
    let time = 0;
    let restBlock = B;

    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        const curHeight = map[i][j];

        if (curHeight > targetHeight) {
          const curRestBlock = curHeight - targetHeight;
          restBlock += curRestBlock;
          time += 2 * curRestBlock;
        } else if (curHeight < targetHeight) {
          const curLackBlock = targetHeight - curHeight;
          restBlock -= curLackBlock;
          time += 1 * curLackBlock;
        }
      }

      if (time > minTime) {
        break;
      }
    }

    if (restBlock < 0) {
      continue;
    }

    if (time <= minTime) {
      minTime = time;

      if (targetHeight > maxHeight) {
        maxHeight = targetHeight;
      }
    }
  }

  console.log(minTime, maxHeight);
}

solution();

 

문제 그대로 구현한 코드이다.

답은 다 맞지만, 시간 복잡도가 O(H*N*M) 이므로 시간초과가 나게된다.

 

성공 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.trim());

const [N, M, B] = input.shift().split(' ').map(Number);
const map = input.map((row) => row.split(' ').map(Number));
const MAX_HEIGHT = 256;

function solution() {
  const { minHeight, maxHeight, heightCountList } = calculateHeightData(map);
  const { minTime, optimalHeight } = findOptimalHeight(
    minHeight,
    maxHeight,
    heightCountList,
    B
  );

  console.log(minTime, optimalHeight);
}

/**
 * 각 높이의 출현 빈도와 최소/최대 높이를 계산하는 함수이다.
 *
 * @param {number[][]} map - N x M 크기의 맵 데이터
 * @returns {Object} - { minHeight, maxHeight, heightCountList }
 */
function calculateHeightData(map) {
  const heightCountList = Array.from({ length: MAX_HEIGHT + 1 }, () => 0);
  let minHeight = Infinity;
  let maxHeight = -Infinity;

  map.forEach((row) =>
    row.forEach((height) => {
      heightCountList[height]++;
      minHeight = Math.min(minHeight, height);
      maxHeight = Math.max(maxHeight, height);
    })
  );

  return { minHeight, maxHeight, heightCountList };
}

/**
 * 주어진 높이 범위에서 최적의 시간을 계산하고, 해당 높이를 반환하는 함수이다.
 *
 * @param {number} minHeight - 맵의 최소 높이
 * @param {number} maxHeight - 맵의 최대 높이
 * @param {number[]} heightCountList - 각 높이의 출현 빈도
 * @param {number} initialBlocks - 초기 블록 수
 * @returns {Object} - { minTime, optimalHeight }
 */
function findOptimalHeight(
  minHeight,
  maxHeight,
  heightCountList,
  initialBlocks
) {
  let minTime = Infinity;
  let optimalHeight = -Infinity;

  for (
    let targetHeight = minHeight;
    targetHeight <= maxHeight;
    targetHeight++
  ) {
    const { time, remainingBlocks } = calculateTimeAndBlocks(
      targetHeight,
      heightCountList,
      initialBlocks
    );

    if (remainingBlocks >= 0 && time <= minTime) {
      minTime = time;
      if (targetHeight > optimalHeight) {
        optimalHeight = targetHeight;
      }
    }
  }

  return { minTime, optimalHeight };
}

/**
 * 특정 목표 높이에서 소요 시간과 남은 블록 수를 계산하는 함수이다.
 *
 * @param {number} targetHeight - 목표 높이
 * @param {number[]} heightCountList - 각 높이의 출현 빈도
 * @param {number} initialBlocks - 초기 블록 수
 * @returns {Object} - { time, remainingBlocks }
 */
function calculateTimeAndBlocks(targetHeight, heightCountList, initialBlocks) {
  let time = 0;
  let remainingBlocks = initialBlocks;

  heightCountList.forEach((count, height) => {
    if (count === 0) return;

    if (height > targetHeight) {
      const removeBlocks = (height - targetHeight) * count;
      time += 2 * removeBlocks;
      remainingBlocks += removeBlocks;
    } else if (height < targetHeight) {
      const addBlocks = (targetHeight - height) * count;
      time += addBlocks;
      remainingBlocks -= addBlocks;
    }
  });

  return { time, remainingBlocks };
}

solution();

 

일단, 변수명과 문법적인 부분은 선언형 프로그래밍과 모듈화를 해보려고 시도해서 코드는 좀 길어졌다.

그 외에도, flat() 함수로 최소 높이와 최대 높이를 구하던 부분도 따로 하지 않고 반복문 하나 안에서 해결했다.

 

원래 사용하던 로직은 크게 달라진 부분이 없다. 단지 시간을 개선하기 위해 값을 미리 저장하는 방법을 사용했다.

어떤 값을 저장하냐면, 기존 맵에서 각 높이의 출현 빈도를 배열에 저장했다.

 

기존에는 모든 배열을 직접 순회하면서 각 높이마다 얼마나 블록을 더하고 빼야하는지 계산했다.

이런 방식을 하게 되면 같은 높이에 대해 얼마나 더하고 뺄건지는 고정 값이므로, (높이의 차이 * 해당 높이의 개수)로 한번에 처리할 수 있다. 이렇게 되면 중복된 값에 대한 계산이 줄고 반복이 줄게 되므로 시간이 단축된다.

 

반복에서 나오지 않은 높이부분은 continue로 반복을 생략하게 되는데, 이런 부분을 넣고싶지 않다면 Map 자료구조를 사용해도 좋을 것 같다는 생각이 든다.