삼각 달팽이

문제 설명

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

풀이

초기 접근 방법

        int totalCellSize = n * (n + 1) / 2;

        int[] answer = new int[totalCellSize];
        
        List<int[]> perimeterNumbers = new List<int[]>();
        
        int number = n;
        int index = 0;
        int nextStart = 1;
        
        while (number > 1)
        {
            int perimeterLength = 3 * number - 3;
        
            perimeterNumbers.Add(new int[perimeterLength]);
        
            for (int i = 0; i < perimeterLength; i++)
            {
                perimeterNumbers[index][i] = nextStart + i;
            }
            
            index++;
            number -= 3;
            nextStart = perimeterLength+1;
        }
        
        if (number == 1)
        {
            perimeterNumbers.Add(new int[]{nextStart});
        }     

• 처음 문제를 접근할 때는 여러 개의 테두리가 겹쳐진다는 점을 활용해 삼각형의 외부 테두리를 2차원 배열로 배치한 후 이를 삼각형 형태에서 1열로 나열할 때의 규칙성을 찾고자 함
• 테두리의 길이는 길이가 n이 주어졌을 때 n + (n - 1) + (n - 2)가 테두리의 길이가 되며 다음 테두리를 길이가 n - 3이 주어졌을 때의 길이로 이어진다는 규칙성을 발견하여 이용하고자 함
• 해당 시행을 반복하다 남은 숫자의 개수가 0 또는 1일 경우가 생기므로 그에 따른 예외 처리를 통해 각각의 테두리로 구성된 2차원 배열을 만들 수 있었으나 이를 배치할 규칙성을 찾지 못해 어려움을 느낌

접근 방식 수정

• 이를 위해 접근 방식을 수정해 삼각형 형태의 배열을 만들고 그 배열에 실제로 숫자를 돌아가면서 배치하는 방법을 구상

public class TriangularSnail
{
    enum Direction
    {
        Down,
        Right,
        Up,
    }

    public static int[] Solution(int n)
    {
        int totalCellSize = n * (n + 1) / 2;

        int[] answer = new int[totalCellSize];
        

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

        int row = -1; //현재 행
        int col = 0; //현재 열
        int num = 1; //이번에 칸에 넣을 숫자

        Direction currentDirection = Direction.Down;

        while (num <= totalCellSize)
        {
            currentDirection = ChooseDirection(row, col, triangle, currentDirection);

            switch (currentDirection)
            {
                case Direction.Down:
                    row++;
                    break;
                case Direction.Right:
                    col++;
                    break;
                case Direction.Up:
                    row--;
                    col--;
                    break;
            }

            triangle[row][col] = num;
            
            num++;
        }

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

        return answer;
    }

    private static Direction ChooseDirection(int row, int col, int[][] triangle, Direction lastDirection)
    {
        if (lastDirection == Direction.Up && triangle[row - 1][col - 1] == 0)
            return Direction.Up;
        if (row + 1 < triangle.Length && triangle[row + 1][col] == 0)
            return Direction.Down;
        if (col + 1 < triangle[row].Length && triangle[row][col + 1] == 0)
            return Direction.Right;
        else
            return Direction.Up;
    }
}

• 이동 방향을 총 3개로 구분함 ; Down, Right, Up
• 이후 삼각형 형태의 배열을 생성

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

• 시작 지점이 될 행과 열 값의 초기값을 설정하고 ChooseDirection 함수를 통해 이동방향을 결정

ChooseDirection 함수

• 현재 위치와 삼각형 배열의 구조 그리고 이전 이동 방향을 고려해 다음 방향을 설정
• 삼각형을 반시계 방향으로 회전하는 구조를 만들어야 하므로 내려갈 때는 해당 위치가 배열을 벗어나지 않으면서 값이 비어있다면 쭉 내려가게 하도록 함
• 배열의 끝에 도달했다면 오른쪽으로 이동하게 함
• 이동하여 배열의 바닥과 오른쪽 끝에 도달했다면 위로 이동하게 함
• 이 경우 위로 이동할 때는 끝에 도달할 때까지 위로 이동해야하므로 비어있지 않은 위쪽 칸을 발견할 때까지 위로 이동하게 함
• 위로 이동하다가 값이 이미 존재하는 칸을 만나면 아래로 내려가며 앞선 내용을 반복

결과 도출

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

• 구성한 triangle 배열을 1열로 나열해 결과를 도출