[프로그래머스] 삼각 달팽이(Java, 자바)

문제

삼각 달팽이

📌 아이디어

문제를 해결하기 위해서는 3방향으로 움직이는 패턴을 찾아야 합니다. 바로 아래, 오른쪽, 위를 반복하며 달팽이가 움직이는 형태입니다.

예를 들어 아래와 같은 2차원 배열이 있다고 가정하면

[1]
[2, 9]
[3, 10, 8]
[4, 5, 6, 7]

먼저 아래 방향으로 1234, 오른쪽 방향으로 567, 위 방향으로 89, 마지막으로 아래 방향으로 10 이동하며 탐색이 종료되게 됩니다.

특정 배열에 arr[x][y] 존재한다면 아래 방향으로 이동할 때는 x+1씩 이동하고, 오른쪽 방향은 y+1씩, 마지막 위 방향으로는 x-1, y-1씩 이동하게 됩니다. 이를 적용하여 다음과 같은 코드를 구성하여 문제를 해결할 수 있습니다.

int x = -1, y = 0, num = 1;
        
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        if (i % 3 == 0) { // 아래 방향
            x++;
        } else if (i % 3 == 1) { // 오른쪽 방향
            y++;
        } else if (i % 3 == 2) { // 위 방향
            x--;
            y--;
        }

        arr[x][y] = num++;
    }
}

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int size = n * (n + 1) / 2;
        int[][] arr = new int[n][n];
        int[] answer = new int[size];
        
        int x = -1, y = 0, num = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i % 3 == 0) {
                    x++;
                } else if (i % 3 == 1) {
                    y++;
                } else if (i % 3 == 2) {
                    x--;
                    y--;
                }
                
                arr[x][y] = num++;
            }
        }
        int idx = 0;
        for (int i = 0; i<n; i++) {
            for (int j = 0; j<n; j++) {
                if (arr[i][j] == 0) {
                    break;
                }
                answer[idx] = arr[i][j];
                idx++;
                
            }
        }
        
        return answer;
    }
}

✏️ TIP

1 . 3가지 방향이 존재하기 때문에 i % 3==0, 1, 2를 작성하여 3 방향이동을 구현해야 합니다.
2. 1부터 N까지의 합은 간단하게 N * (N + 1) / 2로 구현할 수 있습니다.

피드백 및 개선점은 댓글을 통해 알려주세요😊