강의로 돌아가기
타임 오버가 되는 이유가 궁금합니다.(스포 주의)
while로 한 풀이는 시간초과가 되어 통과를 못했는데 그 이유가 궁금합니다.
console.time(), timeEnd()로 하면 오히려 속도가 for문보다 빠르더라구요.
간혹 for문에서 배열.length를 변수화해서 넣어주면 시간이 줄어든다는데 while의 조건문 때문인가요??
아래 코드는 splice를 사용해서 변수화 할 수 없데, splice를 사용해서 풀이할 수 있는 방법이 있는지도 궁금합니다~
// 시간초과로 통과하지 못한 풀이
function solution2(k, m, score) {
let sum =0;
const alignScores = score.sort((a,b)=>b-a);
while(alignScores.length>=m){
const newBox = alignScores.splice(0,m);
sum += newBox.at(-1)*m;
}
return sum;
}
// 통과한 풀이
function solution(k, m, score) {
let sum =0;
const alignScores = score.sort((a,b)=>b-a);
for(let i = 0; i+m <= alignScores.length; i+=m){
sum+= alignScores[i+m-1]*m
}
return sum;
}
/*
// 테스트케이스로 나온 예제를 넣었을때는 while이 더 빨랐습니다.
console.time();
solution(4,3,[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]);
console.timeEnd();
console.time();
solution2(4,3,[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]);
console.timeEnd();
*/
1 개의 답변
배열 메서드의 시간복잡도를 찾아보시면 아실거같네요
같은 로직을 pop으로 처리하기 위해 reverse하여 정렬 순서를 반대로, newBox에는 for문으로 pop의 결과물m번 담았습니다.
나머지는 고친게 없으며 잘 통과합니다.
push와 pop은 O(1)이고 splice는 O(N), shift와 unshift도 O(N)입니다.
JS의 배열은 기본적으로 stack이라서 그런것으로 알고있습니다.
function solution(k, m, score) {
let sum =0;
const alignScores = score.sort((a,b)=>b-a).reverse();
while(alignScores.length>=m){
const newBox = [];
for(let i=0;i<m;i++)newBox.push(alignScores.pop())
sum += newBox.at(-1)*m;
}
return sum;
}
답변 쓰기