백준 20207번

QUESTION LINK

처음 이 문제를 풀 때에는 주어지는 일정들을 모두 오름차순으로 정리한 뒤, 달력 배열에 직접 표기해가면서 끊어지는 상황마다 직사각형의 합을 구해주고자 했습니다. 하지만, 문제의 조건들을 다시 살펴본 결과 두 가지만 고려하면 된다는 것을 파악할 수 있었습니다.

1. 세로길이는 주어지는 일정들을 직사각형으로 만들 때 일정이 겹치는 날이 가장 많은 곳의 개수와 같음
2. 가로길이는 일정이 없는 날이 나오기 전까지 중복합을 해주고, 일정이 없는 날이 나올 시 중복합을 사용함

위 두 가지 조건을 이용해서 문제를 풀면되었기에, 우선 달력에 모든 일정들을 표기하는 작업을 먼저 했습니다.

const [count, ...schedules] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
const calendar = [...Array(365).fill(0)];
// 달력 내의 모든 값들을 0으로 우선 설정

schedules.forEach((schedule) => {
  // 각 일정마다 시작일부터 종료일까지 배열에 맞게 -1을 해주고 달력에 넣어줌
  const [startDay, endDay] = schedule.split(" ").map((v) => +v);
  for (i = startDay - 1; i <= endDay - 1; i += 1) {
    calendar[i] += 1;
  }
});

그리고 이렇게 설정된 달력을 통해서 가로, 세로, 넓이 합을 달력을 순회하면서 구해주도록 했습니다.

calendar.forEach((count, index) => {
  // 달력의 마지막 날이며, 일정이 존재하는 경우
  if (index === 365 - 1 && count) {
    x += 1;
    if (count > y) y = count;
    sum += x * y;
    return;
  }

  // 일정은 없으나 전날까지는 일정이 존재한 경우
  if (!count && x && y) {
    sum += x * y;
    x = 0;
    y = 0;
    return;
  }
  // 일정이 있으나 이전에 일정이 없었던 경우
  if (count && !x) {
    x = 1;
    y = count;
    return;
  }
  // 일정이 이어지는 경우
  if (count && x) {
    x += 1;
    if (count > y) y = count;
  }
});

해당 문제를 풀면서 예외처리를 제대로 해주지 못했던 것은 위 코드에서 가장 첫 조건식이었습니다. 일정이 끝나는 경우는 무조건 ‘일정이 없는 날이 나올 때’라고 고려를 해서 문제를 풀었으나, 달력의 마지막 날이 끝나는 경우에도 일정이 종료되기 때문에 이를 고려해 조건식을 추가했습니다.

기존에 생각했던 풀이 방식보다 새롭게 알게 된 풀이 방식이 훨씬 간단했고, 예외 조건도 잘 고려해주기만 하면 금방 풀 수 있는 문제였습니다. 문제 풀이와 예외 조건에 대한 고민이 더 필요하다는 것을 느꼈습니다.

GITHUB  EMAIL