[프로그래머스][JS / Javascript] n^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

풀이

 

처음에는 아래와 같이 쉽게 구현하였으나 몇몇 테스트케이스에서 런타임에러가 떴다

function solution(n, left, right) {
    let ans = [];
    for(let i=0; i<n; i++)
        for(let j=0; j<n; j++)
            ans.push((i>j ? i : j)+1);
    return ans.slice(left, right+1);
}

 

조건을 다시 보니 n의 값이 상당히 크기 때문에 최적화가 필요해보였고,

이후 필요한 부분만 반복문을 돌도록 코드를 변경해주었다

 

function solution(n, left, right) {
    let ans = [];
    for(let i=Math.floor(left/n); i<=Math.floor(right/n); i++) {
        for(let j=0; j<n; j++) {
            ans.push((i>j ? i : j)+1);
        }
    }

    for(let i=0; i<Math.floor(left%n); i++)
        ans.shift();
    for(let i=0; i<n - Math.floor(right%n) - 1; i++)
        ans.pop();
    
    return ans;
}

 

그랬더니 이제는 시간초과가 난다.

O(n^2)로는 도저히 안되는 깐깐한 문제 같아서 O(n)으로 바꿔줬다

 

function solution(n, left, right) {
    let ans = [];
    for(let x=left; x<=right; x++) {
        let i = Math.floor(x/n);
        let j = Math.floor(x%n);
        ans.push((i>j ? i : j)+1);
    }
    return ans;
}

 

성공!