[JavaScript/Greedy] 백준 골드 5 : 2170 - 선긋기

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

2170번: 선 긋기

---

📌 작성한 코드 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);

겹치지 않는 부분만 확인하면서 더하는 방식으로 진행하였다. 

시작점을 기준으로 정렬하였기 때문에 추후에 시작점이 더 앞선 경우는 발생하지 않으므로, 끝나는 점을 기준으로 확인하고 범위를 더해주면 된다. 

 

✅ 성공