문제

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

정답코드를 바로 보려면 맨아래로 이동

아래의 규칙에 따라 배열을 만든후 잘라서 결과를 출력하는 문제다.

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 > 남기고 나머지는 지웁니다.

만드는 과정은 아래와 같다

• 
• 

입력

• n: 1이상 $10^7$ 이하
• left, right: $0 \leq left \leq right \leq n^2$
  • 단, $left - right < 10^5$

출력

• 위의 과정대로 만들어진 1차원배열

문제 생각하기

간단한 문제라고 생각했었다.
그런데 배열을 너무 많이 사용한 나머지 메모리 초과가 나왔다.

function solution(n, left, right) {
  return Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (j <= i ? i + 1 : j + 1)),
  )
    .reduce((sum, now) => [...sum, ...now], [])
    .slice(left, right + 1);
}

정말 있는 그대로 구현했했다.
배열을 만들고, 이어 붙히고, 잘랐다.
그러면 n이 $10^7$일때 메모리 초과가 나는건 당연했다.

메모리 초과 해결

그래서 배열을 생성하지 않고 for문에서 규칙에 따라 바로 결과를 만들어줬다.
처음의 배열이 생성될때 규칙을 그대로 적용해도 결과는 다르지 않다.

function solution(n, left, right) {
  let now = 0;
  let result = [];

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      if (now >= left && now <= right) {
        result.push(j <= i ? i : j);
      }
      now++;
    }
  }
  return result;
}

하지만 고려하지 않은게 하나 있는데 시간이다!
$n^2$의 속도로 탐색을하면 1014번까지 탐색을 해버린다.
그럼 어떻게할까?

시간 초과 해결

아래와 같은 배열을 만들때를 한번 생각을 해본다.
1 2 3
2 2 3
3 3 3

배열을 만들때 아래처럼 1~9까지의 좌표 두개로 나타낼수 있다.
(1, 1) (1, 2) (1, 3)
(2, 1) (2, 2) (2, 3)
(3, 1) (3, 2) (3, 3)

그럼 7번째 수의 좌표를 알아내려면 어떻게 해야할까?
배열의 크기 n을 알고있으니 몫과 나머지를 사용하면 된다.

n이 3일경우 7번째 수의 좌표는 (나누기결과 올림, 나머지) 이다.
7 / 3 의 몫은 2.333..., 나머지는 1이므로
좌표는 (3, 1)이 나오게 된다.

그리고 이 좌표를 처음에 구했던 규칙에 적용하면 결과가 나온다.
j <= i ? i : j 였는데
나머지 올림 <= 몫 ? 몫 : 나머지 올림으로 바꿔주면 된다.

정답코드

function solution(n, left, right) {
  const result = [];

  for (let i = left + 1; i <= right + 1; i++) {
    const quotient = Math.ceil(i / n);
    const remainder = i % n || n;
    result.push(remainder <= quotient ? quotient : remainder);
  }

  return result;
}