글 읽기 - node.js 로 문제 풀 때 fileread 에러가 있는걸까요?

dbstjddbwls 1년 전 0

기존 백준 문제 풀이 당시 입력 받는 파일을 가져오는 경로 및 코드를 아래와 같이 작성하였습니다.

let input = fs.readFileSync('/dev/stdin').toString().split('\n');

그런데 이상하게 어떠한 코드를 넣든 시간초과가 되었고 코드의 구조나 양을 최대한 단축 시켜보아도 계속 시간초과가 나오는데, 파일을 읽어들이는 부분이 문제인가 싶어 readFileSync의 인자로 경로가 아닌 0을 줘봤습니다.

그런데 이 경우 오류가 나는게 아니라 위 경로로 입력했을 때와 동일하게 시간초과가 나오는데 혹시 node.js로 파일을 읽는데 에러가 있거나 불러오지 못하는 상황일까요?

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');

const TestCaseNum = +input[0];
let aArray = [], bArray = [], cArray = [], dArray = [];

for (let i = 1; i <= TestCaseNum; i++){
    let [a, b, c, d] = [...input[i].split(' ')];
    aArray[i - 1] = +a;
    bArray[i - 1] = +b;
    cArray[i - 1] = +c;
    dArray[i - 1] = +d;
}

let q = []
let p = []

for (let i = 0; i < TestCaseNum; i++) {
    for (let j = 0; j < TestCaseNum; j++) {
        q.push(aArray[i] + bArray[j])
        p.push(-(cArray[i] + dArray[j]))
    }
}

let o = 0;

for (let i = 0; i < q.length; i++) {
    if (q.includes(p[i])) o += 1
}

console.log(o)

adung7 1년 전 0

18번째줄에서부터 23번째줄을 보시면 2중포문이므로 O(N^2)의 시간이 걸리게 됩니다.

N의 최대값인 4000으로 가정하면 16,000,000이고 이는 q와 p에 16,000,000개의 원소가 있다는것을 의미합니다.

따라서 27번째 줄에서 for문 반복 갯수는 최대 16,000,000이고

28번째줄에서 includes메소드를 사용하고 계신데 이는 q의 원소갯수만큼의 시간이 걸리며 O(N)의 시간복잡도입니다.

따라서 16,000,000 + 16,000,000 * 16,000,000 의 시간복잡도를 예상할수있습니다.

이는 수행시간이 가장빠른 C++이라도 제한시간안에 못들어오는 계산량이므로 당연히 시간초과를 받게됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

node.js 로 문제 풀 때 fileread 에러가 있는걸까요?

dbstjddbwls 1년 전 0

adung7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말