brute force
각 트래픽들의 시작점과 끝점을 알아낸다음.
트래픽들을 순회하면서 트래픽 요소의 시작점 부터 끝점까지 0.001 단위로 순회하며 1초 내에 있는 트래픽 갯수를 센다. -> 시간초과 발생한다.
아래 그림과 같다면, 시작점의 순서로 정렬되어있지 않기 때문에
function solution(lines) {
var answer = 0;
// 처리시간은 시작 시간과 끝 시간을 포함한다.
// 33.020 , 0.011 이면 -> 33.010 ~ 33.020
const array = [];
for(let i=0;i<lines.length;i++){
let [,last, time] = lines[i].split(' ')
time = parseFloat(time.split('s')[0]);
last = getSec(last);
array.push([(last-time+0.001).toFixed(3), last.toFixed(3)]);
}
array.forEach(([start,last]) =>{
start = parseFloat(start)
last = parseFloat(last);
for(let i = start; i.toFixed(3) <= last;i = (i + 0.001)){
// start + i * 0.001 ~ start+i*0.001+0.999
const len = array.filter(([ts,tl])=>{
ts = parseFloat(ts);
tl = parseFloat(tl);
// 겹치는 것만 골라낸다.
if(i <= ts && ts < (i + 1)){
return true;
}
if(ts<i && i <=tl){
return true;
}
return false;
}).length;
answer = Math.max(len,answer);
}
})
return answer;
function getSec(time){
const [h,m,s] = time.split(':')
return +h * 3600 + +m * 60 + parseFloat(s);
}
}올바른 풀이
scenario
시작점을 기준으로 정렬했으니 다음과 같은 형태를 갖게될 것이다.
1,3번의 경우 i번째 요소의 끝점에서 부터 1초 내에 있는 갯수만 세면 되지만 2번 같은 경우는 과연 될까?
2번 같은 경우라면 위와 같은 모습이 Worst Case이다. 이 경우, i번째 요소의 맨 끝에서부터 1초 내에 있는 것을 계산하는 것은 최적해가 아니지만, 이 후 요소에서 커버가 되므로, i번째 요소의 끝점에서부터 1초 내 갯수만 세주는 로직이 유효하다.
올바른 풀이 코드(정확한 아이디어)
function solution(lines) {
var answer = 0;
const array = [];
for (let i = 0; i < lines.length; i++) {
let [, last, time] = lines[i].split(" ");
time = parseFloat(time.split("s")[0]);
last = getSec(last);
array.push([parseFloat((last - time + 0.001).toFixed(3)), parseFloat(last.toFixed(3))]);
}
array.sort(([as, al], [bs, bl]) => as-bs);
for (let i = 0; i < array.length; i++) {
const len = array.filter((next) => isOverlab({current:array[i] , next})).length;
answer = Math.max(len, answer);
}
return answer;
function getSec(time) {
const [h, m, s] = time.split(":");
return +h * 3600 + +m * 60 + parseFloat(s);
}
function isOverlab({current,next}){
const [cs,cl] = current;
const [ns,nl] = next;
return (cl <= ns && ns < cl+1) || (ns < cl && cl <= nl);
}
}틀린 아이디어
2번의 경우 때문에 다음 요소의 시작점에서 부터 현재 요소의 끝점까지 반복문을 돌리는 로직을 생각해보았으나, 시간초과발생.
function solution(lines) {
var answer = 0;
// 처리시간은 시작 시간과 끝 시간을 포함한다.
// 33.020 , 0.011 이면 -> 33.010 ~ 33.020
const array = [];
for (let i = 0; i < lines.length; i++) {
let [, last, time] = lines[i].split(" ");
time = parseFloat(time.split("s")[0]);
last = getSec(last);
array.push([(last - time + 0.001).toFixed(3), last.toFixed(3)]);
}
array.sort(([as, al], [bs, bl]) => {
as = parseFloat(as).toFixed(3);
bs = parseFloat(bs).toFixed(3);
return as - bs;
});
for (let i = 0; i < array.length; i++) {
if (i === array.length - 1) {
let [cs, cl] = array[i];
cl = parseFloat(cl);
const len = array.filter(([ts, tl]) => {
ts = parseFloat(ts);
tl = parseFloat(tl);
// 겹치는 것만 골라낸다.
if (cl <= ts && ts < cl + 1) {
return true;
}
if (ts < cl && cl <= tl) {
return true;
}
return false;
}).length;
answer = Math.max(len, answer);
} else {
let [cs, cl] = array[i];
let [ns, nl] = array[i + 1];
cl = parseFloat(cl);
ns = parseFloat(ns);
if (ns < cl + 0.001) {
for (let start = ns; start.toFixed(3) <= cl; start = start + 0.001) {
const len = array.filter(([ts, tl]) => {
ts = parseFloat(ts);
tl = parseFloat(tl);
// 겹치는 것만 골라낸다.
if (start <= ts && ts < start + 1) {
return true;
}
if (ts < start && start <= tl) {
return true;
}
return false;
}).length;
answer = Math.max(len, answer);
}
} else {
const len = array.filter(([ts, tl]) => {
ts = parseFloat(ts);
tl = parseFloat(tl);
// 겹치는 것만 골라낸다.
if (cl <= ts && ts < cl + 1) {
return true;
}
if (ts < cl && cl <= tl) {
return true;
}
return false;
}).length;
answer = Math.max(len, answer);
}
}
}
return answer;
function getSec(time) {
const [h, m, s] = time.split(":");
return +h * 3600 + +m * 60 + parseFloat(s);
}
}
다른 풀이
슬라이딩 윈도우로 풀면 다음과 같다.
시작점을 기준으로 정렬한 뒤, 순회하면서 마감시간을 넣고, 다음 순회의 시작 시간이 마감시간, 마감시간 + 1 사이에 있는지를 확인하여, 만족하는 요소들만 남긴다.
만족하는 요소들은 겹치는 거임
function solution(lines) {
const array = [];
for (let i = 0; i < lines.length; i++) {
let [, last, time] = lines[i].split(" ");
time = parseFloat(time.split("s")[0]);
last = getSec(last);
array.push([parseFloat((last - time + 0.001).toFixed(3)), parseFloat(last.toFixed(3))]);
}
array.sort(([as, al], [bs, bl]) => as-bs);
let answer = 1;
let window = []
array.forEach(([start,end]) =>{
// 현재 시작점
window.push(end);
window = window.filter(e => start < e + 1)
answer = Math.max(answer,window.length)
})
return answer;
function getSec(time) {
const [h, m, s] = time.split(":");
return +h * 3600 + +m * 60 + parseFloat(s);
}
}
Frontend Ninja