[Javascript] 프로그래머스 - 삼각 달팽이

문제 설명

정수 n이 주어졌을 때, 밑변의 길이와 높이가 n인 삼각형을 만들고, 맨 위 꼭짓점에서 반시계 방향으로 달팽이 채우기를 수행합니다. 이후 첫 행부터 마지막 행까지의 값을 순서대로 합쳐 새로운 배열로 반환하는 문제입니다.

---

제한 사항

• n은 1 이상 1,000 이하입니다.

---

해결 방법

알고리즘: 시뮬레이션

1. 초기 설정: n x n 크기의 2차원 배열을 생성합니다.
2. 방향 설정: 아래 → 오른쪽 → 위로 이동하는 방향을 담은 배열 dir을 정의합니다.
3. 반복문을 통해 값 채우기:
   • 현재 방향을 기준으로 값을 채우고, 범위가 끝나면 다음 방향으로 전환합니다.
   • 각 단계에서 현재 이동 범위를 하나씩 줄이며 삼각형 형태로 값을 배치합니다.
4. 최종 배열 합치기:
   • 완성된 배열의 값을 행 순서대로 합쳐 최종 결과를 반환합니다.

---

시간 복잡도

• 시간 복잡도: O(n^2)
  삼각형에 채워질 숫자의 개수는 최대 n(n+1)/2로, 각 숫자를 순차적으로 계산하므로 시간 복잡도는 O(n^2)입니다.
• 공간 복잡도: O(n^2)
  값을 저장하기 위한 n x n 크기의 배열을 사용하므로 공간 복잡도 또한 O(n^2)입니다.

---

구현 코드

function solution(n) {
  let answer = [];
  let map = Array.from({ length: n }, () => []);

  let y = -1;
  let x = 0;
  let num = 1;
  let d = 0;
  let dir = [
    [1, 0],
    [0, 1],
    [-1, -1],
  ];

  for (let i = n; i > 0; --i) {
    for (let j = 0; j < i; ++j) {
      y += dir[d][0];
      x += dir[d][1];
      map[y][x] = num;
      ++num;
    }
    d = (d + 1) % 3;
  }

  for (const row of map) {
    answer.push(...row);
  }

  return answer;
}