삼각형의 외각패턴과 인덱스 활용 - 삼각 달팽이 (Java)

오늘 풀어볼 문제는
프로그래머스의 월간 코드 챌린지 시즌1 문제인
"삼각 달팽이" 입니다.

🐌 삼각 달팽이

문제 설명
정수 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]

🗝️ key point

1) 등차수열의 합

해당 문제는 삼각형을 다루는 문제로
n의 값에 따라 1개씩 늘어가며 층이 쌓이는 정삼각형 구조입니다.

즉, 어떤 높이의 삼각형이든 삼각형을 쌓는데
필요한 블록의 갯수는 등차가 1인 등차수열의 합이라고 볼 수 있습니다.

하여 answer 배열의 크기는 n의 등차수열 합이 됩니다.

int[] answer = new int[n*(n+1)/2];    // 등차수열의 합

2) 삼각형의 외각 패턴

삼각형의 외각 패턴은 각 행마다 숫자가 하나씩 증가하면서 차례로 채워지는 형태의 삼각형을 의미합니다.
이 패턴은 주로 프로그래밍에서 배열 또는 출력 패턴을 생성하는 데 사용됩니다.

아래와 같은 반복문이 바로 삼각형의 외각 패턴을 코드로 간단하게 구현한 것입니다.

public class Main {
    public static void main(String[] args) {
        int n = 4; // 삼각형의 높이 (행의 개수)

        int count = 1; // 출력할 숫자를 나타내는 변수

        // 이중 반복문을 이용하여 삼각형의 외각패턴을 생성
        for (int i = 0; i < n; i++) { // 행을 나타내는 반복문
            for (int j = i; j < n; j++) { // 열을 나타내는 반복문
                // 삼각형의 외각패턴에 따라 숫자를 출력
                System.out.print(count + " ");
                count++; // 다음 숫자로 이동
            }
            System.out.println(); // 행이 바뀌면 줄바꿈
        }
    }
}

출력 값은 다음과 같습니다.

1 2 3 4 
5 6 7 
8 9 
10 

위와 같은 반복문을 사용하면 삼각형의 외각패턴을 구현해낼 수 있습니다.
이를 바탕으로 삼각형의 모양을 배열에 담아보겠습니다.

3) 인덱스 활용

문제에서 요구하는 것은 삼각형을 좌측 대각선으로 내려가고, 아래를 죽 채우고, 우측 대각선으로 올라오는 형태로
값이 담기길 요구하고 있습니다.
그렇기 때문에 삼각형의 외각패턴을 활용하여 이동수를 제한하되
실제 배열에는 값을 넣기 위한 인덱스가 따로 필요합니다.
삼각을 그리기 위해 3가지 패턴으로 나누어 인덱스를 변경해보겠습니다.

위의 3가지 키포인트를 살려서 구현된 코드는 아래와 같습니다.

💻 문제풀이

public int[] solution(int n) {
        int[] answer = new int[n*(n+1)/2];      // 1) 등차수열의 합
        int[][] arr = new int[n][n];            // 그래프

        // 값을 넣고 싶은 인덱스
        int x = -1;
        int y = 0;
        int num = 1;

        // 2) 삼각형의 외각 패턴 (이중 반복문)
        // 6 -> 5 -> 4 -> 3 -> 2 -> 1 번 수행하기 위함
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {

                // 3) 인덱스 활용
                // 왼쪽 -> 바닥 -> 오른쪽 -> .. 반복됨
                // i=0 -> i=1 -> i=2 -> .. 반복되어 아래와 같이 조건문으로 접근 가능

                // 대각선 왼쪽
                if(i % 3 == 0) {
                    x++;
                    
                // 바닥
                } else if(i % 3 == 1) {
                    y++;

                // 대각선 오른쪽
                } else {
                    x--;
                    y--;
                }
                arr[x][y] = num++;
            }
        }

        // 정답 배열에 접근할 인덱스
        int idx = 0;

        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                if(arr[i][j] == 0) break;   // 0인 경우 반복문 빠져나감
                answer[idx++] = arr[i][j];
            }
        }

        return answer;
    }

해당 문제는 이중반복문에서 j=i 값이 들어갈 때 어떤 패턴이 나오는지 파악할 수 있는 좋은 문제였습니다.
또한 i와 j를 이용하여 배열에 접근하는 익숙한 형태를 떠나 반복문으로 접근횟수를 만들어내고,
또 다른 인덱스로 배열을 컨트롤할 수 있다는 점이 새삼 신선하게 다가왔네요.

더 좋은 접근법이 있다면 언제든 댓글 부탁드립니다 :)

출처 ) 프로그래머스 - 삼각 달팽이