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

삼각형 나선형 채우기 문제 해결기

오늘 코딩테스트에서 재미있는 문제를 만났다. 삼각형 모양으로 숫자를 나선형으로 채우는 문제였는데, 처음엔 좀 헷갈렸지만 차근차근 접근해보니 해결할 수 있었다.

문제 이해

n을 입력받아서 1부터 maxN(삼각형의 총 숫자 개수)까지의 숫자를 삼각형의 왼쪽 면을 기준으로 시작해서 아래→오른쪽→위 방향으로 나선형으로 채우는 문제다.

예를 들어 n=4라면:

    1
   2 9
  3 10 8
 4 5 6 7

이런 식으로 채워지고, 결과는 [1,2,9,3,10,8,4,5,6,7]이 되어야 한다.

접근 방법

처음엔 어떻게 접근해야 할지 막막했다. 삼각형을 어떻게 표현할지, 나선형 이동을 어떻게 구현할지 고민이 많았다.

1단계: 삼각형 구조 설계

삼각형을 2차원 배열로 표현하기로 했다. 각 행의 길이는 행 번호+1이 되니까:

const triangle = [];
for (let i = 0; i < n; i++) {
  triangle.push(new Array(i + 1).fill(0));
}

이렇게 하면 삼각형 모양의 배열이 만들어진다.

2단계: 나선형 이동 로직

핵심은 방향 전환 로직이었다. 세 가지 방향이 있다:

• 아래로 (row 증가)
• 오른쪽으로 (col 증가)
• 위로 (row, col 모두 감소)

각 방향에서 더 이상 갈 수 없으면 다음 방향으로 전환하는 방식으로 구현했다.

let direction = 0; // 0=아래, 1=오른쪽, 2=위

if (direction === 0) {
  // 아래로
  if (row + 1 < n && triangle[row + 1][col] === 0) {
    row++;
  } else {
    direction = 1; // 오른쪽으로 전환
    col++;
  }
}

3단계: 경계 조건 처리

가장 까다로운 부분이었다. 각 방향에서 이동할 때:

• 배열 범위를 벗어나지 않는지
• 이미 숫자가 채워진 곳인지

이 두 조건을 모두 체크해야 했다.

최종 코드

function solution(n) {
  // 삼각형의 총 숫자 개수 계산
  const maxN = (n * (n + 1)) / 2;

  // 삼각형 배열 초기화
  const triangle = [];
  for (let i = 0; i < n; i++) {
    triangle.push(new Array(i + 1).fill(0));
  }

  let num = 1;
  let row = 0;
  let col = 0;

  // 방향: 0=아래, 1=오른쪽, 2=위
  let direction = 0;

  while (num <= maxN) {
    triangle[row][col] = num++;

    if (direction === 0) {
      // 아래로
      if (row + 1 < n && triangle[row + 1][col] === 0) {
        row++;
      } else {
        direction = 1; // 오른쪽으로 전환
        col++;
      }
    } else if (direction === 1) {
      // 오른쪽으로
      if (col + 1 < triangle[row].length && triangle[row][col + 1] === 0) {
        col++;
      } else {
        direction = 2; // 위로 전환
        row--;
        col--;
      }
    } else {
      // 위로
      if (row - 1 >= 0 && col - 1 >= 0 && triangle[row - 1][col - 1] === 0) {
        row--;
        col--;
      } else {
        direction = 0; // 아래로 전환
        row++;
      }
    }
  }

  // 결과 배열 생성
  const result = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j <= i; j++) {
      result.push(triangle[i][j]);
    }
  }

  return result;
}

시행착오

처음엔 방향 전환 로직에서 실수가 있었다. 위쪽으로 갈 때 row--, col--를 해야 하는데 row--만 하고 col--를 빼먹었다. 삼각형의 대각선 이동이라 둘 다 감소해야 한다.

또한 경계 조건 체크에서도 실수가 있었다. triangle[row + 1][col] === 0 조건을 빼먹고 단순히 배열 범위만 체크했더니 이미 채워진 곳을 덮어쓰는 문제가 생겼다.

시간복잡도

O(n²)인데, 삼각형의 총 칸 수가 n(n+1)/2이므로 최적이다. 공간복잡도도 O(n²)로 동일하다.

마무리

이런 기하학적 문제는 시각화가 중요하다. 종이에 삼각형을 그려보고 숫자를 채워보면서 패턴을 파악하는 게 도움이 됐다.

방향 전환 로직을 깔끔하게 구현하는 게 핵심이었고, 경계 조건 처리도 꼼꼼히 해야 했다. 다음엔 이런 문제를 더 빠르게 풀 수 있을 것 같다.