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

처리조건

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

풀이

처음에는 주먹구구식방법으로 입력값 n만큼 일차원배열을 가진 이차원배열을 만들고 해당 일차원 배열마다 내부에 1~n만큼 가득채웠다. 그후 이중 for문을 돌면서 완전한 2차원배열을 만들고 1차원배열로 분해해 모두를 concat한 뒤 slice로 letf부터 right까지 짤라서 리턴하려고 했다.

이렇게 1~n까지 들어간 이차원 배열을 만들고 노란색부분만 아래처럼 for문을 돌려 바꿔준뒤 완전한 이차원 배열을 만들고자했다.

function solution(n, left, right) {
  const answer = new Array(n).fill().map((_, index) => {
    return new Array(n).fill(index + 1);
  });

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      answer[i][j] = j + 1;
    }
  }

  let newarr = [].concat.apply([], answer);
  return newarr.slice(left, right + 1);
}

하지만 이렇게 작성하니 간단한 테스트는 통과하나 효율성과 공간사용에서 실패하게된다. n이 10^7까지 범위가 크므로 일정한 규칙을 찾고 left와 right범위내에 있는 값만 배열로 만들어야한다. 우선 (4,7,14)의 입력값으로 만들어내는 완전한 이차원 배열을 그려보자.

여기서 좌표를 그려보면 아래처럼 된다.

이렇게 좌표가 그려지고 자세히 보면 각 (X,Y)에서 X와Y중 큰 값에 +1를 해준값이 해당 자리의 값이된다는 것을 확인 할 수 있다. 여기서 우리는 이제 letf부터 right까지 구해야하므로 여기에 해당하는 값만 구한다면 완전한 이차원 배열을 그리지않고도 빠르게 원하는 범위만 찾아낼 수 있다.

4(1,3) 부터 살펴 보면 1은 left/n을 한 몫을 정수로 나타낸 값이고 3은 left를%n한 값이다 이 둘중 큰 값을 찾아 +1를 해준 값을 answer배열에 담아서 리턴해주면 될 것이다.

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