문제

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

밑변의 길이와 높이가 n인 삼각형에서 아래의 그림을 그려야 한다.

그 후 첫번째 삼각형은 [1, 2, 9, 3, 10, 8, 4, 5, 6, 7]과 같이 출력해준다.
두번째는 [1, 2, 12, 3, 13, 11, 4, 14, 15, 10, 5, 6, 7, 8, 9]
마지막 삼각형은 [1, 2, 15, 3, 16, 14, 4, 17, 21, 13, 5, 18, 19, 20, 12, 6, 7, 8, 9, 10, 11]
과 같이 출력해준다.

문제 접근

규칙만 찾을 수 있다면 쉽게 풀수 있는 문제다.
숫자가 채워지는 순서를 먼저 살펴보면 이렇다

1. 아래로 향한다 (y+1)
2. 오른쪽으로 향한다 (x+1)
3. 왼쪽 대각선 위로 향한다 (y-1, x-1)

이 규칙을 코드로 옮기기 앞서 문제를 한번 더 보면 n이 4일때는
위의 규칙이 실행되는 순서가 1 -> 2 -> 3 -> 1이다.

그리고 숫자를 끝까지 적기위해 움직여야 하는 횟수는
1부터 시작해서 3번 -> 3번 -> 2번 -> 1번이다.

이건 숫자가 5일때도 6일때도 제일 처음에 앞에서 n-1번 움직인후 그 다음도 n-1번을 움직인다.

for, if문으로 이를 구현해도 되긴 하는데 더 간단히 구현하기 위해
숫자를 채워지는 순서를 아래와 같이 변경하고 for문에 들어가기 앞서 Array를 n개 채워준다.

1. 오른쪽으로 향한다 (x+1)
2. 왼쪽 대각선 위로 향한다 (y-1, x-1)
3. 아래로 향한다 (y+1)

완성된 코드는 이렇다.

추가설명

위의 방식으로 for문을 돌다보면 배열에 빈공간을 만들며 채우게 되는데 이는 자바스크립트가 가진 특성때문에 가능한 방법이다. 아마 다른 언어에서는 미리 배열을 0으로 초기화 시킨후 문제를 풀어야 풀릴것같다.

더 정확히 설명하면 자바스크립트의 배열은 희소배열이기에 이런 방법이 가능하다.
희소배열이란 배열의 요소가 메모리상에서 연속적으로 이어져 있지 않은 배열인데 이로인해 유사배열등의 생성도 가능하다.

정답 코드

const solution = n => {
  const answer = Array.from({ length: n }, (_, i) => Array(1).fill(i + 1));
  const pos = [
    [0, 1],
    [-1, -1],
    [1, 0],
  ];
  let x = 0;
  let y = n - 1;
  let now = n;
  let move = n - 1;

  for (let i = 0; i < n; i++) {
    const [ny, nx] = pos[i % 3];
    for (let j = 0; j < move; j++) {
      y += ny;
      x += nx;
      now++;
      answer[y][x] = now;
    }
    move--;
  }
  return answer.flat();
};