[프로그래머스] 삼각 달팽이 (TypeScript로 풀기)

문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해 주세요.

예시 그림

제한사항

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

---

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

---

문제 풀이

어떠한 방식으로 풀어야 할지 고민하다가 1부터 차례대로 배열에 넣게 되면 push와 unshift는 가운데 값을 넣지 못하기에 불가능하다고 생각하였습니다. 따라서 n부터 역순으로 숫자를 넣을 방법을 생각하였습니다. 삼각형의 제일 아래줄을 0층으로 한다면 달팽이의 최종 목적지는 n을 3으로 나눈 몫으로 point라고 하였습니다. 그리고 n에 따라 최종 목적지에 도달하는 방향이 조금씩 다르기에 direction을 n을 3으로 나눈 나머지로 지정을 하였습니다. 마지막 목적지의 값을 넣고 왼쪽으로 이동할 때 혹은 위로 올라갈 때는 unshift형식으로 [addNum,... triagle]으로 Map에 저장을 하고 내려올 때는 우측에 값이 추가되므로 push처럼 [... triagle, addNum]으로 저장을 합니다. 이러한 방식으로 Map에 저장 후 하나씩 반복을 통하여 answer에 추가해 줍니다.

function solution(n: number): number[] {
  let answer = [];
  var triangle = new Map();
  var point: number = Math.floor(n / 3);
  var direction: number = n % 3;
  var addNum: number = (n * (n + 1)) / 2;
  for (let i = 0; i < n; i++) {
    triangle.set(i, []);
  }
  triangle.set(point, [addNum]);
  addNum--;
  for (var i = 1; i <= n + 1 && addNum != 0; i++) {
    for (let j = 0; j < i; j++) {
      if (direction == 0) {
        point--;
      } else if (direction == 1) {
        point++;
      }
      if (point == n || point < 0) {
        break;
      }
      if (direction == 0) {
        triangle.set(point, [...triangle.get(point), addNum]);
      } else {
        triangle.set(point, [addNum, ...triangle.get(point)]);
      }
      addNum--;
    }
    direction = (direction + 2) % 3;
  }
  direction = (direction + 2) % 3;
  for (var i = n - 1; -1 < i; i--) {
    answer.push(...triangle.get(i));
  }
  return answer;
}

 

완료 후 좋은 풀이가 있나 확인을 해보니 Array를 이용하여 빈 배열을 미리 추가해 두고 i와 j를 바꿔가며 반복을 통하여 달팽이의 움직임과 동일한 순서로 배열에 값을 추가하여 줍니다.

function solution(n) {
  let a = Array(n).fill().map((_, i) => Array(i + 1).fill())
  let row = -1
  let col = 0
  let fill = 0
  for (let i = n; i > 0; i -= 3) {
    a[++row][col] = ++fill
    for (let j = 0; j < i - 1; j++) a[++row][col] = ++fill
    for (let j = 0; j < i - 1; j++) a[row][++col] = ++fill
    for (let j = 0; j < i - 2; j++) a[--row][--col] = ++fill
  }
  return a.flat()
}