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

문제 링크

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

풀이 과정

삼각형 밑면의 길이와 높이인 n이 주어지면 맨 위를 기준으로 반시계 방향으로 숫자를 채워나가는 문제입니다.

먼저 높이에 따라 마지막으로 채워지는 숫자(=채워야 되는 빈 칸의 개수)를 정했습니다. 각 높이의 마지막 수는 이전 높이의 수에 자기 자신의 높이만큼을 더한 값이 되므로 아래와 같이 구합니다.

for (int idx = 2; idx <= n; idx++)
  total[idx] = total[idx - 1] + idx;

밑변과 높이가 n으로 일정하므로, n x n 크기의 2차원 배열의 (1, 1) 좌표부터 차례로 ↓, →, ↖︎ 방향으로 탐색을 진행합니다. 현재까지 몇 개의 수를 배열에 채웠는 지 저장하는 cnt 변수를 두고, 진행 도중 total[n] 개를 모두 채우면 탐색을 종료합니다.

while (cnt <= total[n]) {
    while (i <= n && map[i][j] == 0 && cnt <= total[n]) {
        map[i++][j] = cnt++;
    }
    i--;
    j++;

    while (j <= n && map[i][j] == 0 && cnt <= total[n]) {
        map[i][j++] = cnt++;
    }
    j -= 2;
    i--;

    while (map[i][j] == 0 && cnt <= total[n]) {
        map[i--][j--] = cnt++;
    }
    i += 2;
    j++;
}

코드

Java

import java.util.ArrayList;

public class Main {
    public static ArrayList<Integer> solution(int n) {
        ArrayList<Integer> answer = new ArrayList<>();
        int[][] map = new int[n + 1][n + 1];
        int[] total = new int[n + 1];
        total[1] = 1;

        for (int idx = 2; idx <= n; idx++)
            total[idx] = total[idx - 1] + idx;

        int cnt = 1, i = 1, j = 1;

        while (cnt <= total[n]) {
            while (i <= n && map[i][j] == 0 && cnt <= total[n]) {
                map[i++][j] = cnt++;
            }
            i--;
            j++;

            while (j <= n && map[i][j] == 0 && cnt <= total[n]) {
                map[i][j++] = cnt++;
            }
            j -= 2;
            i--;

            while (map[i][j] == 0 && cnt <= total[n]) {
                map[i--][j--] = cnt++;
            }
            i += 2;
            j++;
        }

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (map[i][j] != 0)
                    answer.add(map[i][j]);
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        solution(4);
        solution(5);
        solution(6);
    }
}

Javascript

function solution(n) {
  let answer = [];
  let map = Array.from(Array(n + 1), () => new Array(n + 1));
  let total = new Array(n + 1);
  total[1] = 1;

  for (let idx = 2; idx <= n; idx++) total[idx] = total[idx - 1] + idx;

  let cnt = 1,
    i = 1,
    j = 1;

  while (cnt <= total[n]) {
    while (i <= n && map[i][j] == undefined && cnt <= total[n]) {
      map[i++][j] = cnt++;
    }
    i--;
    j++;

    while (j <= n && map[i][j] == undefined && cnt <= total[n]) {
      map[i][j++] = cnt++;
    }
    j -= 2;
    i--;

    while (map[i][j] == undefined && cnt <= total[n]) {
      map[i--][j--] = cnt++;
    }
    i += 2;
    j++;
  }

  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if (map[i][j] != undefined) answer.push(map[i][j]);
    }
  }

  console.log(answer);

  return answer;
}

solution(4);