백준 20207 / 달력 / JS

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

문제

문제에 주어진 코팅지를 붙이는 규칙에 따라 코팅지의 면적(직사각형의 넓이)을 구하는 문제입니다.

구현

1. 직사각형의 가로와 세로를 구하는 법

문제에 나온 예제 1을 대상으로 설명하면

연속하는 일정들을 포함하는 직사각형의 가로는 연속된 날짜의 길이를 의미하고, 세로는 일정이 쌓인 최대높이를 의미합니다. 따라서 위의 그림을 배열로 기록하면 아래와 같습니다.

2 3 4 5 6 7 8 9 10 11 12 13
1 1 2 3 2 2 1 1  0  1  2  0

2일부터 9일까지 연속된 날짜의 길이는 8일(시작일과 종료일을 포함합니다)이고, 2일부터 9일까지 일정이 쌓인 최대 높이는 [5]에 위치하는 3입니다. 따라서 직사각형의 가로는 8, 세로는 3입니다. 마찬가지로 11일부터 12일까지 연속된 일정의 가로는 2, 세로는 2입니다.

입력값으로 받은 각 일정의 시작일부터 종료일까지의 인덱스에 1을 더해주고, 연속된 일정별로 가로와 세로를 구하면 되겠죠?

혹은 입력값을 '시작일 오름차순, 시작일이 같으면 종료일 내림차순'으로 정렬하면 입력값을 연속된 일정별로 받을 수 있습니다. 연속된 일정이 끊기는 지점에서 이전까지 연속되던 일정의 직사각형을 계산하고 다음 일정의 가로, 세로를 계산해나가는 방식입니다.

코드

정렬을 사용한 방식입니다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n');
const schedule = input.slice(1).map((x) => {
  const tmp = x.trim().split(' ');
  return [Number(tmp[0]), Number(tmp[1])];
});
schedule.push([500, 500]);
let answer = 0;
let width = [-1, -1]; // [시작일, 종료일]
let height = 0;
const calendar = Array(366).fill(0);
const addAnswer = ([start, end], h) => {
  answer += (end - start + 1) * h;
};
schedule
  .sort((a, b) => {
    if (a[0] !== b[0]) {
      return a[0] - b[0];
    } else {
      return b[1] - a[1];
    }
  })
  .forEach((x) => {
    const start = x[0];
    const end = x[1];
    if (start <= width[1] + 1) {
      width[1] = Math.max(width[1], end);
    } else {
      addAnswer(width, height);
      height = 0;
      width = [start, end];
    }
    for (let i = start; i <= end && i <= 365; i++) {
      calendar[i] += 1;
      height = Math.max(height, calendar[i]);
    }
  });

console.log(answer);

연속된 날짜를 'if (start <= width[1])' 와 같이 체크하면 아래와 같은 경우는 연속된 날짜로 인식하지 않습니다.

=> if (start <= width[1] + 1)

공교롭게도 예제 1, 2는 통과합니다. 그러나 아래 테스트케이스에서 걸립니다 ㅎㅎ
(질문검색란에 wldusdh**님이 올려주신 반례를 참고했습니다.)

7
2 4
4 5
5 6
5 7
7 9
10 12
12 12
# 답 : 33

또 width = [0, 0]으로 시작하게 되면 입력값이 [1, 1]부터 들어오기 때문에 'if (start <= width[1] + 1)'조건에 걸려 [0, 0]을 연속된 날짜로 포함합니다. 이는 예제 2에서 걸려 수정할 수 있었습니다.
=> width = [-1, -1]