[일반] 프로그래머스 'n^2 배열 자르기' - js

1. 문제

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

프로그래머스

2. 코드

먼저 빈 배열 초기화 코드를 짜는 과정에서 헤매였던 과정을 살펴보자. 아래는 내가 처음 짠 코드이다.

function solution(n, left, right) {
  let arr = new Array(n).fill(new Array(n).fill(0)) // n*n 크기 2차배열을 0으로 초기화
  for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
        arr[i][j]=Math.max(i+1,j+1) // i행, j열 중 큰숫자로 채워넣기
    }
  }
}

// arr
[ [ 3, 3, 3 ], [ 3, 3, 3 ], [ 3, 3, 3 ] ]

arr를 new Array fill 방식을 사용하니 행열 속 각 열에 있는 배열? 들이 하나가 된 듯 변경된다. 처음엔 3중 for문을 썼는데 계속 저렇게 하나인 냥 변경돼서 정말 ptsd 오는 줄 알았다. 내가 for문의 조건을 제대로 짠 것 같은데도 결과가 이상하게 나와서 30분 이상을 헤맸다.

내가 의도한 바 대로 짜기 위해서는 arr를 다음과 같이 할당 해주었어야 한다. 오늘 이 문제를 통해 하나 또 배워간다. 찾아보니 2차원 배열을 만들 때는 Array.from을 사용한다고 한다.

// 각 열에 해당하는 배열들이 다른 열의 배열들에게 영향을 주지 않는 2중 배열 만드는 방식인 듯 하다.
Array.from({length: n},()=>new Array(n).fill(0))

해당 방법을 잘 알아두자!

function solution(n, left, right) {
  let arr = Array.from({length: n},()=>new Array(n).fill(0)) // n*n 크기 2차배열을 0으로 초기화
  for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
        arr[i][j]=Math.max(i+1,j+1) // i행, j열 중 큰숫자로 채워넣기
    }
  }
}

하지만 '1 <= n <= 10^7' 다음의 조건에 의해 모든 배열의 값들을 세팅해주는 방법을 사용하면 타임아웃이 나온다. 규칙을 찾아서 우리가 원하는 부분에 해당하는 배열의 값들만 찾으라는 얘기다.

배열을 만들 때 사용했던 방법을 다시 한번 보자. 각 배열의 값에는 해당 칸의 행과 열 번호 중 큰 수가 들어간다.

arr[i][j]=Math.max(i+1,j+1)

 

1차원 배열에서의 index와 2차원 배열에서의 i 및 j 와의 규칙을 찾으면 위의 식을 사용하여 arr[index]에 해당하는 값을 찾을 수 있다.

   2차원            1차원
0,0 0,1 0,2       0, 1, 2
1,0 1,1 1,2  =>   3, 4, 5
2,0 2,1 2,2       6, 7, 8

i의 값을 살펴보자.

0,0,0 => 1,1,1 => 2,2,2
0,1,2 => 3,4,5 => 6,7,8

i의 값은 1차원 index의 값을 n으로 나눈 후 소수점을 버린 몫과 같다.

이제 j의 값을 자세히 보자.

0,1,2 => 0,1,2 => 0,1,2
0,1,2 => 3,4,5 => 6,7,8

j의 값은 1차원 index의 값을 n으로 나눈 나머지와 같다. 이 규칙을 수식으로 표현하면 다음과 같다.

i=Math.floor(index/n)
j=index%n

이제 이를 수식으로 표현해보자.

arr[i][j] = arr[index] = Math.max(Math.floor(index/n)+1,(index%n)+1)

이로써 1차원 배열의 index만 알고 있어도 해당 index에 해당하는 값을 구할 수 있게 되었다.

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

 

문제에 들인 시간에 비해 정답 코드는 매우 간단했다. 역시 수학적 규칙을 찾는 문제는 어렵지만 재밌다. 2차원 배열 초기화에 시간을 너무 많이 쓰다니~~!!ㅠㅠ 내가 너무 배열을 만드는 데에만 집착했던 것 같다. 배열이 먼저 만들어져야 문제를 풀 수 있다는 생각만 했지, 규칙을 찾을 생각은 못했기 때문에...(복기할 때도 저렇게 풀어야겠다는 생각을 못했다. 복기의 의미가 있니? 읍읍)

복기

5/26