[백준/28070] 유니의 편지쓰기- JavaScript

문제분류 : 백트래킹

난이도 : 골드 5

출처 : 백준 - 유니의 편지쓰기

문제

제한사항

📌 내가 생각한 풀이

누적합을 이용하여 시간복잡도를 줄여주자. 만약 idx=1 ~ idx=3까지의 기간이라고 하면 idx=1을 +1 해주고 idx=4(3+1)에 -1해주어 누적합을 적용하면 1 1 1 0 이 됨을 이용하자.

let inputs = require("fs")
  .readFileSync("boj_28070_유니의 편지쓰기.txt")
  .toString()
  .trim()
  .split("\n");

function solution(input) {
  let n = +input[0];
  let max = 0;
  let idx = 0;
  let arr = new Array(100000).fill(0);
  let sum = new Array(100000).fill(0);
  sum[0] = arr[0];
  for (var i = 1; i < 1 + n; i++) {
    let [start, end] = input[i].split(" ");
    let [sY, sD] = start.split("-").map(Number);
    let [eY, eD] = end.split("-").map(Number);
    let sI = (sY - 2000) * 12 + sD - 1;
    let eI = (eY - 2000) * 12 + eD - 1;
    arr[sI] += 1;
    arr[eI + 1] -= 1;
  }
  for (var i = 1; i < sum.length; i++) {
    sum[i] = arr[i] + sum[i - 1];
    if (sum[i] > max) {
      max = sum[i];
      idx = i;
    }
  }
  let month = 2000 + Math.floor(idx / 12);
  let day = (idx % 12) + 1;
  if (Math.floor(day / 10) > 0) {
    console.log(`${month}-${day}`);
  } else {
    console.log(`${month}-0${day}`);
  }
}
solution(inputs);

📌 느낀점

처음 프로그래머스에서 풀었을 때 신기함을 느꼈던 누적합유형이다. 프로그래머스의 파괴되지 않은 건물 문제와 비슷하므로 다시한번 풀어보자!