[백준] 2304 창고 다각형 JavaScript

혅·2024년 9월 12일

백준, 프로그래머스 -JavaScript-

목록 보기

137/215

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
지붕의 가장자리는 땅에 닿아야 한다.
비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

예제 입력

7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

예제 출력

내가 했던 풀이 방법

입력받은 column을 기둥 위치를 기준으로 오름차순 정렬해준다.
column 배열에서 가장 큰 높이와 그 위치를 저장한다. reduce를 이용해주었다.
height를 가장 멀리있는 위치 크기만큼의 배열로 선언하고 null로 초기화해준다. (null보다 0으로 하는 것이 추후 area를 계산할 때 좋다. 원래 같은 최대 높이가 2개 이상 있을 때를 대비해 null로 두었는데, 가장 첫번째로 나타나는 최대 높이를 기준으로 나누었기 때문에 의미 없어졌다.)
index를 0으로 초기화해준다. 입력받은 column은 모든 위치에 기둥이 존재하지 않을 수 있기 때문에 index를 두어 column과 height를 따로 관리해주어야 한다.
가장 처음 기둥이 위치하는 곳부터 최대 높이가 있는 위치까지 일단 height를 계산한다. 만약 column[index][0]가 i가 아닐 경우에는 해당 위치에 기둥이 없다는 의미이기 때문에 이전 height를 그대로 가져간다. 해당 위치에 기둥이 있다면 이전 기둥들에 비해 height가 큰지 작은지에 따라 다르게 계산한다. 이전 기둥들에 비해 크다면 현재 위치의 height 값을 height 배열에 저장해준다. 작거나 같다면 이전 height 값을 그대로 가져간다.
최대 높이가 있는 위치까지 height를 계산해주었다면, 가장 오른쪽에서 다시 최대 높이가 있는 곳까지 반대방향으로 height를 계산해주어야 한다. 이번에는 index를 column.length-1로 설정하고, i를 가장 멀리있는 기둥부터 최대 높이 전까지 i를 줄이면서 5번 내용을 반복한다. 다만, 이때는 방향이 반대이므로 이전 height 값이 아닌 다음 height 값을 가져가야 한다.
5번 6번의 결과로 height에는 각 위치에 창고의 height가 저장되어 있다. height의 값을 모두 더해주면 창고의 면적이 나온다.

코드

const fs = require('fs');
let [N, ...column] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
for (let i = 0; i < N; i++) {
  column[i] = column[i].trim().split(' ').map(Number);
}

column.sort((a, b) => {
  if (a[0] > b[0]) return 1;
  else return -1;
});

let max = column.reduce(
  (acc, array) => {
    const value = array[1];

    if (value > acc.maxHeight) {
      return {
        maxHeight: value,
        maxIndex: array[0],
      };
    }
    return acc;
  },
  { maxHeight: 0, maxIndex: null }
);

let index = 0;
let height = Array.from({ length: column[column.length - 1][0] }, () => null);

for (let i = column[0][0]; i <= max.maxIndex; i++) {
  if (column[index][0] !== i) {
    height[i] = height[i - 1];
  } else {
    if (column[index][1] < height[i - 1]) {
      height[i] = height[i - 1];
    } else if (column[index][1] > height[i - 1]) {
      height[i] = column[index][1];
    } else {
      height[i] = height[i - 1];
    }
    index++;
  }
}

index = column.length - 1;
for (let i = column[column.length - 1][0]; i > max.maxIndex; i--) {
  if (column[index][0] !== i) {
    height[i] = height[i + 1];
  } else {
    if (column[index][1] < height[i + 1]) {
      height[i] = height[i + 1];
    } else if (column[index][1] > height[i + 1]) {
      height[i] = column[index][1];
    } else {
      if (i === column[column.length - 1][0]) height[i] = column[index][1];
      else height[i] = height[i + 1];
    }
    index--;
  }
}

let sum = 0;
for (let i = 0; i < height.length; i++) {
  if (height[i]) sum += height[i];
}

console.log(sum);