2283 구간 자르기 (자바스크립트)

문제

수직선(數直線) 상에 구간 N개가 있다. 임의의 두 정수 A, B(A < B)를 정하여, 각 구간에서 A와 B 사이에 포함되지 않은 부분을 모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

입력

1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다.

2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다.

출력

두 정수 A, B를 출력한다. 조건을 만족하는 A, B가 존재하지 않으면 “0 0”을 출력한다.

조건을 만족하는 A, B가 여러 개 존재할 때는 A가 가장 작은 경우를 출력한다. 그것도 여러 개 존재할 때는 B가 가장 작은 경우를 출력한다.

====

문제 풀이

인덱스 s 와 e를 0 으로 초기화 한 뒤 만약 s부터 e까지의 선분들의 합이 m보다 작다면 e를 증가시키고 크다면 s를 감소시켰다.

이때 선분들의 합이 k라면 s와 e를 바로 출력하면 된다.

이를 위해 각 구간 별 선분들의 갯수와 누적 합 배열을 통해 어떤 구간부터 어떤 구간까지의 선분의 길이 합을 구할 필요가 있었다.

만약 입력값 [s,e] 배열을 통해 s부터 e를 방문하며 +1 씩 했다면 최대 10억의 연산이 반복되어 시간 초과가 발생한다. 

N의 시간 복잡도로 이를 처리하는 방식으로는 우선 lines라는 배열을 선언하여 선분의 시작점에 +1 , 선분의 끝지점의 다음에 -1을 해놓는다. 끝지점의 다음이 선분이 변하는 지점이기 때문이당. 이제 1부터 최댓값까지 탐색하면서 이전 인덱스에 기록된 값을 계속해서 더해주면 구간 당 존재하는 선분 갯수를 기록할 수 있다.

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

const [n, k] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) => s.split(' ').map(Number));

const MAX = Math.max(...arr.map(([_, e]) => e));

const lines = new Array(MAX + 2).fill(0);

for (const [s, e] of arr) {
    lines[s + 1] += 1;
    lines[e + 1] -= 1;
}

for (let i = 1; i < MAX + 1; i++) {
    lines[i] += lines[i - 1];
}

위에서 구한 구간 별 선분 갯수를 통해 누적 합 배열을 만들 수 있고 이를 통해 구간 별 총 길이를 구할 수 있다.

const sum = new Array(MAX + 1).fill(0);

for (let i = 1; i < MAX + 1; i++) {
    sum[i] = sum[i - 1] + lines[i];
}

sum[ j ] - sum [i] 는 i부터 j 까지의 선분 총 길이가 구해진다.

이제 s,e를 0,0으로 선언한 뒤 

sum[e]-sum[s] 가 k보다 작다면 e를 ++ , 크다면 s++를 해준다. 이때 구간에 있는 선분의 합이 k와 같다면 바로 종료하면 된다.

let s = 0;
let e = 0;

while (s <= e) {
    const diff = sum[e] - sum[s];
    if (diff === k) {
        console.log(s, e);
        process.exit(0);
    }
    if (diff < k) {
        e++;
    } else {
        s++;
    }
}

console.log(`0 0`);

 

정답 코드

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

const [n, k] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) => s.split(' ').map(Number));

const MAX = Math.max(...arr.map(([_, e]) => e));

const lines = new Array(MAX + 2).fill(0);

for (const [s, e] of arr) {
    lines[s + 1] += 1;
    lines[e + 1] -= 1;
}

for (let i = 1; i < MAX + 1; i++) {
    lines[i] += lines[i - 1];
}

const sum = new Array(MAX + 1).fill(0);

for (let i = 1; i < MAX + 1; i++) {
    sum[i] = sum[i - 1] + lines[i];
}

let s = 0;
let e = 0;

while (s <= e) {
    const diff = sum[e] - sum[s];
    if (diff === k) {
        console.log(s, e);
        process.exit(0);
    }
    if (diff < k) {
        e++;
    } else {
        s++;
    }
}

console.log(`0 0`);