[백준] 2170 선 긋기 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0]);
let arr = new Array(n);
for (let i = 0; i < n; i++) {
  let [a, b] = input[i + 1].split(" ").map(Number);
  arr[i] = [a, b];
}
arr.sort((a, b) => a[0] - b[0]);

let ans = 0;
ans += arr[0][1] - arr[0][0];
let cur = arr[0][1];
for (let i = 1; i < n; i++) {
  if (arr[i][0] <= cur && arr[i][1] > cur) {
    ans += arr[i][1] - cur;
    cur = arr[i][1];
  }
  if (arr[i][0] > cur) {
    ans += arr[i][1] - arr[i][0];
    cur = arr[i][1];
  }
}
console.log(ans);

✔ 알고리즘 : 정렬

✔ x좌표를 기준으로 오름차순 정렬한다.

✔ cur은 현재 직선의 끝점을 가르킨다. 첫번째 직선의 y좌표를 cur로 지정한 후 탐색을 시작한다.

✔ 현재 직선의 x좌표가 cur보다 작은 경우
무조건 겹치는 부분이 생기는 직선이다. 현재 직선의 y좌표를 보고 cur보다 작으면 겹쳐지는 직선이므로 continue, cur보다 크면 길이의 총 합이 증가할 수 있는 직선이므로 arr[i][1] - cur을 ans에 더해주고 cur 좌표를 갱신

✔ 현재 직선의 x좌표가 cur보다 큰 경우
새로운 직선의 시작점을 찍어야 하는 경우이다. arr[i][1] - arr[i][0] 을 ans에 더해주고 cur 좌표를 갱신

✔ 난이도 : 백준 기준 골드 5