[백준] 18866 젊은 날의 생이여 (Javascript)

문제

BOJ18866_젊은 날의 생이여

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const young = Array.from({ length: N }, () => Array(2));
const old = Array.from({ length: N }, () => Array(2));

let youngMinHappy = Number.MAX_SAFE_INTEGER;
let youngMaxTired = 0;
let oldMaxHappy = 0;
let oldMinTired = Number.MAX_SAFE_INTEGER;

// 젊은 날
for (let i = 0; i < N; i++) {
    if (arr[i][0] < youngMinHappy && arr[i][0] !== 0) youngMinHappy = arr[i][0];
    if (arr[i][1] > youngMaxTired && arr[i][1] !== 0) youngMaxTired = arr[i][1];

    young[i][0] = youngMinHappy;
    young[i][1] = youngMaxTired;
}

// 늙은 날
for (let i = N - 1; i >= 0; i--) {
    if (arr[i][0] > oldMaxHappy && arr[i][0] !== 0) oldMaxHappy = arr[i][0];
    if (arr[i][1] < oldMinTired && arr[i][1] !== 0) oldMinTired = arr[i][1];

    old[i][0] = oldMaxHappy;
    old[i][1] = oldMinTired;
}

let answer = -1;
for (let i = 1; i < N; i++) {
    if (young[i - 1][0] > old[i][0] && young[i - 1][1] < old[i][1]) answer = i;
}
console.log(answer);

풀이

이 문제가 이해하기 어려우니 작게 쪼개어 보자.

1. 먼저, N년간 욱제의 행복도와 피로도가 주어진다. 행복도와 피로도는 양의 실수 값을 가진다. 어떤 1 ≤ K < N에 대해 1, 2, …, K년은 욱제의 젊은 날이고, K + 1, K + 2, …, N년은 욱제의 늙은 날이다.

   N이 주어졌을 때,
   젊은 날: 1 ~ K
   늙은 날: K+1 ~ N

2. 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
   임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.

   젊은 날이 늙은 날보다 더 행복하고, 덜 피로하다.
   즉,
   젊은 날의 행복도의 최솟값은 늙은 날의 행복도의 최댓값보다 크다. (젊은 날의 행복도 > 늙은 날의 행복도)
   젊은 날의 피로도의 최댓값은 늙은 날의 피로도의 최솟값보다 작다. (젊은 날의 피로도 < 늙은 날의 피로도)

즉, N과 1~N년 까지의 행복도와 피로도가 주어졌을 때 젊은 날(1 ~ K)과 늙은 날(K+1 ~ N)을 구분하기 위한 K를 구해야 한다.
그리고 위에 나와있는 젊은 날과 늙은 날의 기준에 따라 필요한 정보는 아래 네 가지가 있다.

• 젊은 날의 행복도의 최솟값
• 젊은 날의 피로도의 최댓값
• 늙은 날의 행복도의 최댓값
• 늙은 날의 피로도의 최솟값

위 조건을 토대로 코드를 작성해보면 아래와 같이 작성할 수 있다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map((e) => e.split(' ').map(Number));

const happy = [];
const tired = [];
arr.forEach(([u, v]) => {
    happy.push(u);
    tired.push(v);
});

let answer = 0;

for (let i = 1; i < N; i++) {
    let youngHappyMin = Math.min(...happy.slice(0, i));
    let oldHappyMax = Math.max(...happy.slice(i));
    let youngTiredMax = Math.max(...tired.slice(0, i));
    let oldTiredMin = Math.min(...tired.slice(i));

    if (youngHappyMin > oldHappyMax && youngTiredMax < oldTiredMin) answer = i;
}

console.log(answer ? answer : -1);

입력받은 행복도와 피로도를 각각의 배열로 나누어서 관리하고 1부터 N까지 반복문을 수행하며 조건에 부합한지 확인한다.
코드는 깔끔하지만 위 코드의 시간 복잡도는 O(N$^5$) 이다.
slice(0,i), slice(i) = O(N) 이게 두 번 있으니 O(N$^2$), 그리고 각각에 대해 Math.min(), Math.max() 를 수행하니 O(N$^2$) 이 둘을 곱하면 O(N$^4$) 이걸 N번 반복하니 총 O(N$^5$)이 된다. 이는 N이 50만 되어도 경우 연산을 약 3억 번 정도 수행하기 때문에 시간초과가 발생한다.

또한 행복도와 피로도로 0이 주어졌을 때는 행복도, 피로도가 0이라는 뜻이 아니라 누락되었다는 뜻이기 때문에 0이 입력되었을 경우는 반영하지 말아야 하기에 아래와 같이 코드를 추가해주어야 한다.

...

for (let i = 1; i < N; i++) {
    let youngHappyMin = Math.min(...happy.slice(0, i).filter((e) => e !== 0));
    let oldHappyMax = Math.max(...happy.slice(i).filter((e) => e !== 0));
    let youngTiredMax = Math.max(...tired.slice(0, i).filter((e) => e !== 0));
    let oldTiredMin = Math.min(...tired.slice(i).filter((e) => e !== 0));

    if (youngHappyMin > oldHappyMax && youngTiredMax < oldTiredMin) answer = i;
}

...

이럴 경우 filter의 시간 복잡도까지 더해져서 시간이 기하급수적으로 증가하여 시간 초과 판정을 받는다.

따라서 미리 젊은 날의 대한 최솟값, 최댓값에 대한 정보를 young 배열에 저장해두고, 늙은 날의 대한 최솟값, 최댓값에 대한 정보를 old 배열에 저장해둔 뒤 1~N까지 순회하며 미리 저장해둔 young 배열과 old 배열을 참조하여 조건에 부합하는지 확인할 수 있다.

이렇게 되면 연산 횟수는 3N이고 이를 빅오 표기법으로 표기하면 O(N)의 시간복잡도로 표현할 수 있고 N의 범위는 1,000,000까지 이기 때문에 통과할 수 있다.

참고

문제 풀이
filter 메서드의 시간 복잡도
slice 메서드의 시간 복잡도