https://www.acmicpc.net/problem/2170
2170번: 선 긋기
첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.
www.acmicpc.net
📌 작성한 코드 1
// 2170
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = Number(input[0]);
const lines = [];
for (let i = 1; i <= N; i++) {
lines.push(input[i].split(" ").map(Number));
}
lines.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const newLines = [lines[0]];
for (let j = 1; j < lines.length; j++) {
const [s2, e2] = lines[j];
let flag = false;
for (let i = 0; i < newLines.length; i++) {
const [s1, e1] = newLines[i];
if (s2 <= e1) {
let newStart = s1 < s2 ? s1 : s2;
let newEnd = e1 < e2 ? e2 : e1;
newLines[i] = [newStart, newEnd];
flag = true;
break;
}
}
if (!flag) newLines.push([s2, e2]);
}
const answer = newLines.reduce((sum, [s, e]) => {
return sum + (BigInt(e) - BigInt(s));
}, BigInt(0));
console.log(answer.toString());
겹치는 부분 합치면서 배열 업데이트 하는 방식을 적용하였다.
(BigInt 필요할까 해서 사용했는데 범위를 넘지 않는 것 같다. 사용하지 않아도 문제가 통과한다.)
📌 작성한 코드 2
// 2170
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = Number(input[0]);
const lines = [];
for (let i = 1; i <= N; i++) {
lines.push(input[i].split(" ").map(Number));
}
lines.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
let answer = 0;
let last = -Infinity;
for (let i = 0; i < lines.length; i++) {
const [s, e] = lines[i];
if (last <= s) {
answer += e - s;
last = e;
} else if (s <= last && e >= last) {
answer += e - last;
last = e;
}
}
console.log(answer);
겹치지 않는 부분만 확인하면서 더하는 방식으로 진행하였다.
시작점을 기준으로 정렬하였기 때문에 추후에 시작점이 더 앞선 경우는 발생하지 않으므로, 끝나는 점을 기준으로 확인하고 범위를 더해주면 된다.
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DFS] 백준 골드 3 : 9466 - 텀 프로젝트 (0) | 2024.02.22 |
|---|---|
| [JavaScript/DP] 백준 실버 1 : 11057 - 오르막수 (0) | 2024.02.20 |
| [JavaScript/Greedy] 백준 골드 5 : 11000 - 강의실 배정 (0) | 2024.02.19 |
| [JavaScript/DP] 백준 실버 3 : 11727 - 2xn 타일링 2 (0) | 2024.02.17 |
| [JavaScript/DP] 백준 실버 2 : 1912 - 연속합 (0) | 2024.02.17 |