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

문제

프로그래머스

 

풀이

  (1) 문제에서 요구한 2차원 배열을 초기화한다.
  (2) flat 메서드를 이용하여 1차원 배열로 변환한다.
  (3) 요구사항에 맞게 left에서 right까지 잘라서 답을 return한다.

 

시간초과

2차원 배열을 생성할 때, 2차원 배열을 1차원 배열로 변환할 때 각각 O(n^2)의 시간이 소요된다..

function solution(n, left, right) {
    const answer = [];
    const matrix = Array.from({ length: n }, (_, i) =>  
        Array.from({ length: n }, (_, j) => Math.max(i + 1, j + 1))
    );
    
    const flatArr = matrix.flat();
    
    for (let i = left; i <= right; i++) {
        answer.push(flatArr[i]);
    }
    
    return answer;
}

 

해결

2차원 배열을 생성하지 않아도 주어진 조건 left와 right에서 해당 요소의 행과 열을 알 수 있다.

function solution(n, left, right) {
    const answer = [];
    
    for (let i = left; i <= right; i++) {
        const row = Math.floor(i / n); 
        const col = i % n;            
        answer.push(Math.max(row + 1, col + 1));
    }
    
    return answer;
}

결론

레벨2의 월간 코드 챌린지 문제이다.

문제의 요구 사항에서 n의 최대값은 10^7이므로 2차원 배열로 처리하면 시간 초과가 발생한다.