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

문제 링크 : 코딩테스트 연습 > 월간 코드 챌린지 시즌3 > n^2 배열 자르기

---

문제 설명

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

---

제한사항

• 1 ≤ n ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

---

입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

---

문제 풀이

1. 2차원 배열에 값이 채워지는 규칙

• n = 3, left = 2, right = 5로 생성되는 배열이 아래와 같고 좌표는 (x, y)라고 하겠습니다.

  [
      [1, 2, 3],
      [2, 2, 3],
      [3, 3, 3],
  ]

  x	y	값
  0	0	1
  0	1	2
  0	2	3
  1	0	2
  1	1	2
  1	2	3
  2	0	3
  2	1	3
  2	2	3

• 규칙이 보이시나요?
• 바로 바로 x와 y 중 큰 수에 1을 더한 것이 값이 됩니다.
• 코드로는 Max(x, y) + 1 게 되죠.
  

2. 결과 배열 생성

• 제한사항으로 n이 10^7 까지 될 수 있기 때문에 2차원 배열 전체를 만들어 놓고 left, right로 추출하는 것은 효율성이 좋지 않아요.
• 그럼 left ~ right 범위에 해당하는 값만 생성하는 방법은 없을까?
• 좌표를 통해서 값을 생성하는 것은 위에서 알아 보았으니 범위내에서 좌표를 찾을 수 있다면 완성되겟죠?
• 위의 예시에서 범위는 left(2) ~ right(5)가 되고 n = 3일 때 우리가 찾아야 하는 좌표는 [0, 2], [1, 0], [1, 1], [1, 2]이 됩니다.
• 범위내의 값을 i라고 할때

  i	n	몫	나머지
  2	3	0	2
  3	3	1	0
  4	3	1	1
  5	3	1	2

• 규칙이 보이시나요?
• x = Math.floor(left / n)
• y = left % n

코드

function solution(n, left, right) {
    var answer = [];

    for (let i = left; i <= right; i++) {
        answer.push(Math.max(Math.floor(i / n), i % n) + 1)
    }

    return answer;
}