[Programmers LEVEL2] 삼각 달팽이

📗 문제 내용

[문제 링크]

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

[문제]

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

[제한 사항]

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

🧑🏼‍💻 나의 풀이

문제에서 주어진 그림을 이차원 배열로 생각하여 (n=6일 때 예시)

[
    [ 1 ],
    [ 2,    ],
    [ 3,   ,    ],
    [ 4,   ,   ,    ],
    [ 5,   ,   ,   ,    ],
    [ 6,   ,   ,   ,   ,    ]
]

answer[0][0]부터 answer[5][0]까지를 먼저 채우고,

[
    [ 1 ],
    [ 2,    ],
    [ 3,   ,    ],
    [ 4,   ,   ,    ],
    [ 5,   ,   ,   ,    ],
    [ 6,  7,  8,  9, 10, 11 ]
]

그 다음 answer[5][1]부터 answer[5][5]

[
    [ 1 ],
    [ 2, 15 ],
    [ 3,   , 14 ],
    [ 4,   ,   , 13 ],
    [ 5,   ,   ,   , 12 ],
    [ 6,  7,  8,  9, 10, 11 ]
]

그 다음 answer[4][4]부터 answer[3][3] -> answer[2][2] -> answer[1][1]

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

그리고 다시 answer[2][1]부터 answer[4][1]까지 채워나가는 방식을 생각하여 작성했다. 나의 풀이 코드는 다음과 같다.

function solution(n) {
  const answer = [];
  let number = 1; // 시작 숫자

  // 이차원 배열 answer의 각각 행과 열을 가리키는 인덱스
  let r = -1,
    c = 0;

  // 1 ~ n까지 (피라미드)층 수만큼 loop
  for (let i = 1; i <= n; i++) {
    // 예를 들어, 4층이면 처음(i=1)에는 4번, 두 번째(i=2)에는 3번, 세 번째(i=3)에는 2번...
    // 반복해야하므로 j=0 ~ j=n-i까지 loop
    for (let j = 0; j <= n - i; j++) {
      // 아래로 내려가거나, 오른쪽으로 가거나, 위로 올라가거나 3가지 방향이 있을 수 있으므로
      // 3으로 나눈 나머지를 기준삼아 각각 다음 행과 다음 열을 결정했다.
      if (i % 3 === 1) r += 1;
      else if (i % 3 === 2) c += 1;
      else {
        r -= 1;
        c -= 1;
      }
      if (!answer[r]) answer[r] = [];
      answer[r][c] = number;
      number += 1;
    }
  }
  console.log(answer);
  /*
    [
      [ 1 ],
      [ 2, 15 ],
      [ 3, 16, 14 ],
      [ 4, 17, 21, 13 ],
      [ 5, 18, 19, 20, 12 ],
      [ 6,  7,  8,  9, 10, 11 ]
    ]
   */
  
  // flat() 메서드는 모든 하위 배열 요소를 재귀적으로 이어붙여 새로운 배열을 만들어준다.
  // 즉, 2차원 배열이 1차원 배열로 합쳐져서 출력된다.
  return answer.flat();
}

console.log(solution(6));
// [1, 2, 15, 3, 16, 14, 4, 17, 21, 13, 5, 18, 19, 20, 12, 6, 7, 8, 9, 10, 11];

다른 사람의 풀이

function solution(n) {
  const answer = [];
  const totalNumber = (n * (n + 1)) / 2;
  const dx = [1, 0, -1];
  const dy = [0, 1, -1];
  let x = 0;
  let y = 0;
  const matrix = Array.from(new Array(n), () => new Array(n).fill(0));
  let direction = 0;

  for (let i = 1; i <= totalNumber; i++) {
    matrix[x][y] = i;
    const nx = x + dx[direction];
    const ny = y + dy[direction];
    if (nx >= n || ny >= n || nx < 0 || ny < 0 || matrix[nx][ny] !== 0) {
      direction = (direction + 1) % 3;
      x += dx[direction];
      y += dy[direction];
      continue;
    }
    x = nx;
    y = ny;
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      answer.push(matrix[i][j]);
    }
  }
  return answer;
}

방향을 미리 dx, dy 배열에 설정해놓고 direction으로 x, y를 결정하여 문제를 해결하신 모습이다.

Reference

• https://rutgo-letsgo.tistory.com/182
• https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/flat