[JS] 프로그래머스 코딩테스트 연습 | L2 n^2 배열 자르기

문제 링크

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

문제 설명

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

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.

2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.

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

   • 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.

4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

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

입출력 예

n	left	right
3	2	5
4	7	14

문제 풀이

문제 설명만 보고 금방 풀겠네 했는데 아니었다ㅎㅎ
n의 범위가 커서 계속 런타임 에러가 났다

1차 시도

function solution(n, left, right) {
  let array = [];
  let arr = [];

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      i >= j ? arr.push(i) : arr.push(j);
    }
    array.push(arr);
    arr = [];
  }

  array = array.reduce((acc, cur) => {
    return acc.concat(cur);
  });

  return array.splice(left, right - left + 1);
}

2차 시도

여전히 시간 초과 에러 발생

function solution(n, left, right) {
  let array = [];

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      i >= j ? array.push(i) : array.push(j);
    }
  }

  return array.slice(left, right + 1);
}

정답

계속 시간 초과가 난 이유

n의 범위가 107 까지 있기 때문에 코드를 정말 빡빡하게 짜야 합니다.

문제에서 left와 right를 제시한 만큼 left 전 의미없는 값들과 right 후 의미없는 값들은 아예 만들지 않고
스킵하는 방식으로 코드를 짜야 합니다.

참조: 질문하기

example

n: 4 | left: 7 | right: 14 | result: [4,3,3,3,4,4,4,4]

좌표에서 x,y 값 구하는 방법
x = floor(i / n) --> 정수만
y = i % n

| 1(0, 0) | 2(0, 1) | 3(0, 2) | 4(0, 3) |
| 2(1, 0) | 2(1, 1) | 3(1, 2) | 4(1, 3) |
| 2(2, 0) | 3(2, 1) | 3(2, 2) | 4(2, 3) |
| 4(3, 0) | 4(3, 1) | 4(3, 2) | 4(3, 3) |

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