[프로그래머스] 삼각 달팽이 (시뮬레이션)

문제

정수 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]

생각

• 배열 초기화: 삼각형 모양이 되도록 2차원 동적 배열을 초기화

• 방향 설정: 현재 위치를 기준으로, 달팽이의 이동 방향을 3가지로 정의

  • 아래: (1,0) 행 번호 증가
  • 오른쪽: (0,1) 열 번호 증가
  • 위: (-1, -1) 행, 열 번호 감소

• 방향 전환: 삼각형의 경계를 만나면 방향 directionType 변경.

directionType = (directionType + 1) % 3;

• 달팽이 이동: 달팽이가 이동할 때마다 원소의 값 num을 1씩 증가

triangle[x][y] = num++;

• 결과 기록: 전체 원소의 개수 = n (n+ 1) / 2이므로 여기에 동적 배열을 돌면서 결과 기록

코드

public class TriangularSnail {

    static final int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, -1 } }; // 아래, 오른쪽, 위

    public int[] solution(int n) {

        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
        }

        int num = 1;
        int x = 0, y = 0; // 시작 위치
        int directionType = 0; // 0: 아래, 1: 오른쪽, 2: 위

        while (num <= n * (n + 1) / 2) {
            triangle[x][y] = num++;

            int newX = x + dir[directionType][0];
            int newY = y + dir[directionType][1];

            if (newX >= 0 && newX < n && newY >= 0 && newY <= newX && triangle[newX][newY] == 0) {
                x = newX;
                y = newY;
            } else {
                // 방향 전환
                directionType = (directionType + 1) % 3;
                x = x + dir[directionType][0];
                y = y + dir[directionType][1];
            }
        }

        int[] answer = new int[(n * (n + 1)) / 2];

        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                answer[idx++] = triangle[i][j];
            }
        }

        return answer;
    }
}

정리

• 방향 전환을 구현하는 것이 핵심이었던 문제였다. 처음에는 코드의 이해를 쉽게 하기 위해서 방향을 0, 1, 2가 아닌 BELOW, RIGHT, UP과 같은 String으로 선언하는 방법도 생각해 보았지만, 방향 전환을 위한 새로운 메서드를 생성해야 하는 등 코드의 길이가 불필요하게 길어지는 문제가 발생했다. 결국, 간결성과 효율성을 유지하기 위해 방향을 정수 상수로 사용하는 것이 더 나은 선택이었다고 생각한다.