[Algorithm] n^2 배열 자르기 ( Programmers - JavaScript )

문제 설명

정수 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^7

* 0 <= left <= right <= n2

* right - left <= 10^5

 

 

 

---

 

 

 

입출력 예

 

 

 

 

---

 

 

 

입출력 예 설명

 

입출력 예 #1

* 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

 

입출력 예 #2

* 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

 

 

---

 

 

 

문제풀이

이 문제는 정리하자면, 2차원 배열을 1차원배열로 만들어주고 left, right 만큼의 배열값만 추출하면 되는 단순한 문제처럼 보였다.

 

그렇기 때문에 맨처음에 접근한 방식은 아래와 같이 2차원 배열을 만들어주고, 1차원 배열로 정리 후 원하는 값만 추출하는 방식으로 접근하였다.

function solution(n, left, right) {
  const answer = [];
  const arr = new Array(n);
  for (let i = 0; i < arr.length; ++i) arr[i] = new Array(n);
 
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
      arr[i][j] = Math.max(i, j) + 1;
    }
  }
 
  arr.forEach((array) => answer.push(...array));
 
  return answer.slice(left, right + 1);
}

 

하지만, 이런 방식의 단점은 10^7의 길이를 여러개 만들어서 메모리가 감당 못하는 경우가 생겼다.

 

그래서 2차원 배열은 없이 아래처럼 1차원 배열만 생성했지만 역시 펑~

function solution(n, left, right) {
  let arr = [];
 
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      arr.push(i);
    }
    for (let j = i + 1; j <= n; j++) {
      arr.push(j);
    }
  }
 
  return arr.slice(left, right + 1);
}

 

 

결국 해결하는 방법은 아래와 같다. left / n 으로 row, column 의 맨 앞부분만 찾고 해당하는 길이만큼만 넣어주면 해결된다.

function solution(n, left, right) {
  const answer = [];
 
  while (left <= right)
    answer.push(Math.max(Math.floor(left / n), left++ % n) + 1);
 
  return answer;
}

 

 

왜냐하면, 1,1 자리에서부터 left, right는 상수로 정해주기 때문에 4개가 필요하다면 1,1 > 1,2 > 1,3 > 1,4 만 순서대로 넣어주면 되는것이다.

 

n = 3, left = 2, right = 5 일 경우로 해서 좀 더 시각적으로 보자면, 2차원 배열을 만들면 아래와 같이 생성된다.

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

 

위의 배열이 1차원 배열이 되면 [1, 2, 3, 2, 2, 3, 3, 3, 3] 이 될것이고, left = 2 는 1차원 배열의 2번인덱스에서부터 right = 5 는 1차원 배열의 5번인덱스까지의 값만 추출하는 것이다. 그러면 [3, 2, 2, 3]만 추출하면 되는 것이다.

 

 

 

 

 

 

 

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

프로그래머스