n^2 배열 자르기

그냥 쉽게 풀려고 했는데, 생각대로 되지 않아 시간내에 푸는걸 실패했다. 이쯤되면 난 알고리즘에 재능이 없는것 같기도... 일단 계속 풀어보자

문제

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

프로그래머스

첫 생각

처음에 문제를 제대로 이해하질 못했는데, 1행 1열 부터 i행 i열 까지라는 의미를 제대로 파악하지 못했다. 그런데 예제 코드를 통해 설명하는 부분을 보면서 의미를 알게 되었다. 예를 들어 i = 1 이라면 (1,0)(1,1)(0,1) 모두 포함된다. 그냥 2차원 배열에서 순차적으로 행부터 내려온다고 계산했다가 잘못된 것을 깨닫고 조건을 다시 잘 살펴보았다.

 

특징이 있다면, 행으로 판단해보고자 했다. 첫 행은 당연하게도 1,2,3,4,...n 까지 나올 것이다. 그 다음은 두번째 행.

행렬의 index 가 i 보다 작다면 자연스럽게 이전 값이 반복된다. 즉, 2,2,3,4,...n 의 형태가 나온다. 다음 행도 마찬가지다.

3,3,3,4,5,...n 의 형태로 진행이 될 것이다. 결국 마지막은 n,n,n,n,...n 이 될 것이다.

 

문제에서는 이러한 2차원 배열은 1차원 배열로 변경하라고 지시하고 있다. 난 이러한 방향에 충실하게 코드를 작성해보았다.

function solution(n, left, right) {
  // 2차원 배열 만들기
  const arr = Array.from(Array(n), () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i > j) {
        arr[i][j] = i + 1;
      } else {
        arr[i][j] = j + 1;
      }
    }
  }
  let concatArr = arr[0];
  for (let i = 1; i < n; i++) {
    concatArr = concatArr.concat(arr[i]);
  }
  const resultArr = concatArr.slice(left, right + 1);
  return resultArr;
}

2차원 배열을 생성한다음, 각 반복문을 통해 i > j 일 경우 그대로 i + 1 을 적용하고, 아니라면 j + 1 을 통해 순차적으로 숫자가 증가하도록 하였다. 이후 concat 을 활용해서 배열 하나하나를 합치고, 지정된 범위만큼의 배열을 return 했다. 테스트 케이스는 성공적으로 통과했다.

 

하지만 실제 제출을 하니, 시간초과가 발생했다! 

 

바보처럼 조건을 제대로 살펴보지 않았다. 

시간복잡도 상 중첩반복을 사용할 수 없다.

조건상 중첩반복을 사용할 수 없다. 여기서 좀 맨탈이 나갔다가, 다시 생각을 해보니 결국 2차원배열을 만들 필요가 있을까 라는 생각이 들었다. 결국 1차원배열로 변경해야하며, 답에서 요구하는것은 문제에서 주어진 left, right 범위 내의 배열이다. 문제의 조건을 보니 left 와 right 의 범위는 10^5 로서 충분히 반복을 돌릴만한 수치였다.

 

여기까지 생각할때 시간 초과... 어쩔 수 없었지만 나 자신과의 약속이 있으니, 먼저 코드를 참고하기로 하였다. 

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

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

  return answer;
}

역시나 left 에서 right 까지의 범위를 지정하여 범위를 지정하였다. 이후 여기서 중요한데, 참 머리가 좋으시다... 

 

처음에 2차원 배열이 아니라 1차원 배열로서 해결해야한다고 생각했을 때, 일정한 규칙이 있었다. 예를 들어서 

 

• i = 1 이라면, n = 4 라고 가정하면, 1행은 [1,2,3,4] 가 된다. 
• i = 2 이라면, n = 4 라고 가정하면, 2행은 [2,2,3,4] 가 된다.
• i = 3 이라면, n = 4 라고 가정하면, 3행은 [3,3,3,4] 가 된다.
• i = 4 이라면, n = 4 라고 가정하면, 4행은 [4,4,4,4] 가 된다.

어느정도 규칙이 보인다. i 가 1이면 1번 반복, i 가 2이면 2가 2번 반복, i 가 3이면 3이 3번 반복.... 이런식이다. 

이걸 1열로 나열했을 때, 인덱스 left 부터 right 까지의 배열을 가져오라고 했으니, 요는 left 위치일 때의 값일 것이다. 

이 때 left 인덱스를 n 으로 나누어 주면 (나머지 버린다면) 시작 포인트를 알 수 있게 된다. 

예를 들어 left 가 7 이라면, n = 4 라면, 7/4 = 1(버림) 이기에, i = 2 이라는걸 알 수 있다. 

 

여기에 추가할 부분은 i = 2 가 만드는 배열 원소 중 값이 어떤것인지를 알아야 된다. 순차적으로 값이 증가하기에 나머지를 이용하면 될 듯 한다. 나머지를 통해 7 % 4 = 3 임을 알았다. 0,1,2,3 이기에 3은 n=4 일 때 가장 마지막이다. 따라서 4다. 

 

왜 이럴까 생각해보면 결국 반복되는 수가 n만큼 연속된 수의 합이기 때문이다. 따라서 어떠한 값도 n을 초과할 수 없는 것이다. 그렇기에 인덱스를 나머지계산 하였지만, 그 인덱스의 나머지값이 곧 배열의 원소인 점을 주의하자.

 

인덱스를 n으로 나눈 나머지값과, 인덱스를 n으로 나눈 몫을 비교하여 둘 중 큰 값을 배열에 넣어주면 된다.

---

문제를 정리하면서도 개념적으로 햇갈리는걸 보아하니 틀릴만 했다.. 잘 기억해두자