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

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 전형적인 배열 채우기 문제의 유형이었다고 생각합니다. 이 문제를 풀기 앞서 코드업의 '2차원 배열 달팽이 채우기'를 문제를 먼저 풀어본다면 많은 참고가 될 수 있습니다.

 

[코드업 - 1484] 2차원 배열 달팽이 채우기 4-1 - Java

 

우선 문제에서 주어지는 수 n에 따라 삼각형에서 달팽이 채우기를 할 수 있는 전체 요소의 개수는 ((n + 1) * n / 2)개입니다. 이때 n * n 2차원 배열을 만들어 주어 문제에서 나타내는 삼각 달팽이를 다음과 같이 구성하고자 했습니다.

 

 

위 그림대로 배열을 채우는 로직은 다음과 같습니다. ↓, ↗, ← 이렇게 3개의 흐름이 달팽이 형태를 그리며 반복되는 것을 확인할 수 있기에, 하나의 반복문 내에 3개의 분기를 나누어 처리해주도록 했습니다.

 

        int i = 0, j = 0, r1 = n - 1, c1 = n - 1, r2 = 0, c2 = 0;

        for (int num = 1; num <= total; num++) {
            d[i][j] = num;
            if (i < r1 && j == c2) {
                i++;
            } else if (j > c2 && i == r2) {
                j--;
                if (d[i][j] != 0) {
                    i++;
                    j++;
                    r1 -= 2;
                    c1 -= 2;
                    r2++;
                    c2++;
                }
            } else if (i > r2 && j < c1) {
                i--;
                j++;
            }

 

이렇게 구성하고난 뒤에는 다음과 같이 배열을 빗금 형식으로 읽어 결과값 배열을 반환합니다.

 

이때 각 빗금에는 일종의 규칙이 존재합니다. 예를 들어 2번째 빗금에 속하는 좌표는 (1, 0), (0, 1)인데, 각 좌표의 행 및 열의 합은 모두 1로 동일합니다. 또한 3번째 빗금에 속하는 좌표는 (2, 0), (1, 1), (0, 2)로 모두 2로 동일 합니다. 이런식으로 빗금이 하나씩 추가될 때마다 좌표들의 합은 몇번째 빗금인지에 따라 결정됩니다. 이러한 규칙상을 바탕으로 배열을 빗금 형식으로 읽는 로직으로 나타내면 다음과 같습니다.

 

        int index = 0;
        for (int line = 0; line < n; line++) {
            for (int col = 0; col < n; col++) {
                for (int row = 0; row < n; row++) {
                    if (line == row + col) {
                        answer[index++] = d[row][col];
                        break;
                    }
                }
            }
        }

 

나의 소스 코드

class Solution {

    public int[] solution(int n) {
        int total = (n + 1) * n / 2;
        int[] answer = new int[total];

        int[][] d = new int[n][n];
        int i = 0, j = 0, r1 = n - 1, c1 = n - 1, r2 = 0, c2 = 0;

        for (int num = 1; num <= total; num++) {
            d[i][j] = num;
            if (i < r1 && j == c2) {
                i++;
            } else if (j > c2 && i == r2) {
                j--;
                if (d[i][j] != 0) {
                    i++;
                    j++;
                    r1 -= 2;
                    c1 -= 2;
                    r2++;
                    c2++;
                }
            } else if (i > r2 && j < c1) {
                i--;
                j++;
            }
        }

        int index = 0;
        for (int line = 0; line < n; line++) {
            for (int col = 0; col < n; col++) {
                for (int row = 0; row < n; row++) {
                    if (line == row + col) {
                        answer[index++] = d[row][col];
                        break;
                    }
                }
            }
        }

        return answer;
    }
}

 

참고자료

• https://school.programmers.co.kr/learn/courses/30/lessons/68645