글 읽기 - JS로 시간복잡도에 관해 수정해보았습니다.

dbstjddbwls 1년 전 0

이전 질문에서 시간복잡도에 대한 문제를 지적받아 반으로 나눠 해봤는데 이 또한 시간초과가 납니다... Javascript 이분탐색에 대해 알아보았는데 while로 사용하는 것으로 보이는데, 예시가 모두 단 한 번의 숫자만 찾는 것으로 나오는데 이 문제처럼 특정 배열을 순회하며 있는지 찾는 경우를 못 찾아서 최대한 비슷하게 짜봤는데도 이건 좀 아니다 싶은 느낌입니다... 혹시 제가 감을 못 잡고 있는 방향성이 어느 쪽인지 알 수 있을까요?? JS 알고리즘 관련하여 최근 시작했는데 좀 갈팡질팡 하는 느낌입니다...

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const TestCaseNum = +input[0];

let aArray = [], bArray = [], cArray = [], dArray = [], q = [], p = [];

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 o = 0;

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]))
    }
}

q.sort(function(a,b){return a-b})
p.sort(function(a,b){return a-b})

const mid = Math.round(q.length / 2);

for (let i = 0; i < p.length; i++) {
    if(q[mid] < p[i] && q.slice(mid).includes(p[i]) ||
      q[mid] > p[i] && q.slice(0,mid).includes(p[i]) ||
      q[mid] === p[i]){
        o += 1
    }
}

console.log(o)

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

문제

문제

출처

ICPC

JS로 시간복잡도에 관해 수정해보았습니다.

dbstjddbwls 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말