반응형
문제
설명
구현 방법은 다양할 수 있다.
시간복잡도를 고려해야 통과할 수 있다.
right - left + 1만큼만 반복문을 돌릴 수 있는 방법을 생각해보자.
틀린 코드
1. 처음부터 끝까지 2차원 배열을 생성하고
2. 1차원 배열로 변환한 후
3. left부터 right까지 slice한다.
하지만 n이 10^7까지 될 수 있어서 역시 이 방법으로는 통과할 수 없었다.
function solution(n, left, right) {
let answer = [];
let arr = [];
for(let i = 1; i <= n; i++){
let tmp = [];
for(let j = 1; j <= n; j++){
tmp.push(Math.max(i,j));
}
arr.push(tmp);
}
return [].concat(...arr).slice(left,right+1);
}통과한 코드
1. i는 left의 몫부터 right의 몫까지 반복문을 돌린다.
2. j는 1부터 n까지 반복문을 돌리되, cur의 값이 left와 right의 사이일때만 arr에 값을 push한다.
단점 : cur를 계산하느라 시간이 소요된다.
function solution(n, left, right) {
let arr = [];
for (let i = Math.floor(left / n) + 1; i <= Math.floor(right / n) + 1; i++) {
for (let j = 1; j <= n; j++) {
let cur = (i - 1) * n + j - 1;
if (left <= cur && cur <= right) {
arr.push(Math.max(i, j));
}
}
}
return arr;
}개선한 최종 코드
깔끔하게 딱 right - left + 1만큼만 반복한다.
function solution(n, left, right) {
let arr = [];
for (let i = left; i <= right; i++) {
let r = Math.floor(i / n) + 1;
let c = (i % n) + 1;
arr.push(Math.max(r, c));
}
return arr;
}
