[Lv.2] n^2 배열 자르기

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.

• 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.

3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ n ≤ 10⁷
• 0 ≤ left ≤ right < n²
• right - left < 10⁵

풀이

먼저 이 문제는 매개변수의 범위가 엄청나게 크다. 최악의 경우 기본이 O(10^7)이다.

따라서 문제에서 주어진 순서대로 풀려고 해서는 통과할 수가 없는 문제이다. 이런 문제의 특성상 무조건 규칙이 존재한다.

• n = 1 -> [[1]] -> [1]
• n = 2 -> [[1, 2], [2, 2]] -> [1, 2, 2, 2]
• n = 3 -> [[1, 2, 3], [2, 2, 3], [3, 3, 3]] -> [1, 2, 3, 2, 2, 3, 3, 3, 3]
• n = 4 -> [[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]

이제 규칙이 보일 것이다. 행과 열의 번호에 따라 쉽게 구할 수 있음이 보인다.

따라서 굳이 2차원 배열을 구하지 않아도 1차원 배열로 바로 풀 수 있는 문제이다.

여기서 중요한 점은 시간과 메모리를 최소화시켜야 한다. 그러지 않으면 한 번 반복하더라도 시간초과, 메모리 초과가 뜰 수 있기 때문이다.

시간과 메모리를 위해 이 문제에서 중요시 봐야할 것은 left와 right 매개변수이다.

위에서 1차원 배열을 바로 구할 수 있다고 했다. 그러면 굳이 1차원 배열도 n만큼 다 구할 필요가 없는 것이다.

따라서 left와 right 사이만 구하면 되는 것이다.

left와 right 사이만 구하기 위해서는 처음 시작 행과 열의 번호를 알아야 한다.

먼저 행은 left / n이고, 열은 left % n이다. 이것만 알면 이 문제는 끝이다.

통과 코드

function solution(n, left, right) {
  var oneArray = []; // 수들이 들어갈 1차원 배열
  var colum = left % n; // 열
  var row = Math.floor(left / n); // 행(js에는 //가 없음)
  
  for (var i = 0; i <= right - left; i++) { // left와 right 사이만큼만 반복
    if (colum === n) { // 열의 번호와 n이 같아지면 열 번호를 되돌리고 행을 추가해줘야 함
      colum = 0;
      row++;
    }
    // 행이 더 클 때에는 행 번호를 추가하고 열이 더 클때에는 열 번호를 추가
    colum < row ? oneArray.push(row + 1) : oneArray.push(colum + 1);
    colum++;
  }
 
  return oneArray;
}