[백준2170_자바스크립트(javascript)] - 선 긋기

🔴 문제

선 긋기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, ...inputs] = fs.readFileSync(path, 'utf-8').trim().split('\n');
const lines = inputs
  .map((it) => it.split(' ').map(Number))
  .sort((a, b) => a[0] - b[0] || a[1] - b[1]);

let ans = 0;
let start = lines[0][0];
let end = lines[0][1];

for (let i = 0; i < Number(n); i++) {
  const [nStart, nEnd] = lines[i];

  if (nStart <= end) {
    if (end <= nEnd) end = nEnd;
    else continue;
  } else {
    ans += end - start;
    start = nStart;
    end = nEnd;
  }
}

ans += end - start;

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

가능한 선의 위치가 매우 크기 때문에 자료구조를 사용하는 것 보다 겹치는 두 선분을 합선하고, 안겹치는 선분끼리만 합해서 답을 내야겠다고 판단했다.
먼저 겹치는 선분들을 찾기 위해 입력받은 선분들을 1. 시작점 기준, 2. 시작점이 같다면 끝점 기준으로 정렬했다.
먼저 비교 대상인 선분의 시작점과 끝 점을 start, end 라는 변수에 할당했다. 그 다음 선분들을 하나씩 비교하면서 합선할지, 분리할 지 정해야 하는데 입력받은 점들을 시작점 기준으로 정렬해주면 나올 수 있는 경우의 수가 단 세가지 뿐이다.

1. 대상 선분의 end가 다음 선분의 nStart보다 크거나 같고, end가 nEnd보다도 큰 경우, 이 때는 대상 선분이 다음 선분을 포함하는 형태이므로 어떠한 연산을 할 필요없이 continue해준다.
2. 대상 선분의 end가 다음 선분의 nStart보다 크거나 같고, end가 nEnd보다도 작은 경우, 이 때는 두 선분이 겹치므로 대상 선분의 끝 점만 다음 선분의 끝 점으로 바꿔주면 된다.

if (end <= nEnd) end = nEnd;

3. 두 선분이 겹치지 않는 경우에는 이전 선분을 ans 변수에 누적합 해주고, 다음 선분을 현재 선분으로 업데이트 해부면 된다.

위 연산들이 모두 끝나면 마지막 선분은 처리가 되지 않은 상태일 텐데 이 경우만 마지막에 고려해주면 된다.

🔵 Ref