[Javascript] n^2 배열 자르기 (87390)

 

문제링크

코딩테스트 연습 - n^2 배열 자르기

 

접근 방법

처음에는 문제에서 친절하게 가야하는 방향을 하나씩 알려주어서
순진하게 따라 풀었다..

하지만 1 <= n <= 10^7 이라는 범위이기 때문에
2차원 배열을 만들어 값을 채운 O(n^2)의 시간복잡도는 통과할 수 없었다.

때문에 left와 right가 2차원 행렬에서 어떤 위치에 있는지 패턴을 찾아야 한다.

n = 3, left = 2, right = 5
1 2 3                                    
2 2 3                                 
3 3 3   => 1 2 3 2 2 3 3 3 3

n = 4, left = 7, right = 14 일때
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4 => 1 2 3 4 2 2 3 4 3 3 3 4 4 4 4 4

직접 그려보니 패턴이 눈에 보인다.

left    =>   left / n 행, left % n 열
right  =>   right / n 행, right % n열
즉, 둘다 /n, %n으로 좌표를 구할 수 있다.

2차 행렬에서 좌표의 값은 Math.max(x, y) + 1로 나타낼 수 있으니 이제 답을 구할 수 있다.

 

// 패턴을 찾아 풀이한 코드

function solution(n, left, right) {
    var answer = []
    
    while(left <= right){
        answer.push(Math.max(Math.floor(left / n) , left % n) + 1);
        left++;
    }
    
    return answer
}

// 행렬을 만들어 푼 코드

function solution(n, left, right) {
    const arr = new Array(n).fill(0).map(() => Array(n))
    
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            arr[i][j] = Math.max(i, j) + 1;
        }
    }
    
    const arrConcat = arr.reduce((acc,cur) => {
      return acc.concat(cur);
    });
    
    return arrConcat.slice(left, right+1)
}