Programmers | Level 2 | 삼각 달팽이

Programmers | Level 2 | 삼각 달팽이

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Simulation

󰧭 Description

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

 Constraints

• 1 ≤ n ≤ 1,000

󰦕 Examples

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]

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int[] solution(int n) {
        // 삼각형 배열 초기화
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];  // 각 행의 길이는 해당 행 인덱스에 따라 증가
        }
        
        int number = 0;  // 채워 넣을 숫자
        int x = -1;      // 시작 위치 (아래로 이동하기 위해 x를 -1로 초기화)
        int y = 0;       // y는 초기화된 상태에서 그대로 유지
        
        // 삼각형을 반시계 방향으로 채우기
        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 {
                    x--;  // 대각선 위로 이동
                    y--;
                }
                number++;
                triangle[x][y] = number;  // 현재 위치에 숫자 채우기
            }
        }
        
        // 1차원 배열로 변환 후 결과 반환
        int[] result = new int[number];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                result[index] = triangle[i][j];  // 삼각형 배열의 값을 1차원 배열에 복사
                index++;
            }
        }
        
        return result;  // 최종 결과 반환
    }
}

 Approach

이 문제는 주어진 정수 n을 기반으로 삼각형 모양의 2차원 배열을 생성하고, 이를 달팽이 모양으로 채워나가는 시뮬레이션 문제입니다. 각 숫자가 달팽이 형태로 배열에 채워진 후, 이 배열을 1차원 배열로 변환하여 반환해야 합니다. 주요 알고리즘은 반복적으로 삼각형의 각 변을 따라 이동하면서 숫자를 채우는 방식으로 이루어집니다.

1. 문제 분석

이 문제는 주어진 n에 대해 삼각형 모양의 배열을 만들고, 이를 반시계 방향으로 달팽이 모양으로 채우는 것입니다. 이 문제는 다음과 같은 요소를 고려해야 합니다:

• 삼각형의 구조: 삼각형은 각 행이 위로 갈수록 짧아지는 형태로, 행의 인덱스가 증가할수록 배열의 길이도 증가합니다.
• 반시계 방향 채우기: 삼각형을 채우는 순서는 아래, 오른쪽, 대각선 위로 이어지며 반복됩니다. 이 방향을 고려하여, 배열의 위치를 추적하며 숫자를 채워야 합니다.
• 1차원 배열로 변환: 최종적으로, 삼각형 배열을 1차원 배열로 변환하여 결과를 반환해야 합니다. 이는 문제의 출력 형식을 만족시키기 위한 중요한 단계입니다.

2. 접근 방식

이 문제를 해결하기 위해, 주어진 삼각형 구조를 반시계 방향으로 숫자를 채우는 시뮬레이션을 수행합니다.

• 삼각형 배열 초기화: n 크기의 2차원 배열을 초기화하고, 각 행의 길이는 해당 행의 인덱스에 따라 증가시킵니다.
• 숫자 채우기: 삼각형의 각 변을 따라 숫자를 채우며, 아래 → 오른쪽 → 대각선 위의 순서로 이동합니다. 이 과정은 삼각형이 완전히 채워질 때까지 반복됩니다.
• 1차원 배열로 변환: 채워진 삼각형을 1차원 배열로 변환하여 최종 결과로 반환합니다.

이 문제에서 가장 난해한 부분은 바로 아래 → 오른쪽 → 대각선 위의 순서로 이동하며 숫자를 채우는 방식입니다. 이 이동을 구현하기 위해서는 현재 위치와 방향을 지속적으로 추적해야 합니다. 방향을 바꾸는 규칙은 삼각형의 변에 따라 반복되므로, 이를 규칙적으로 처리하는 것이 핵심입니다. 이러한 규칙만 찾아내면 되는데 떠올리는 게 참 쉽지가 않습니다. 😓

3. 삼각형 배열 초기화

먼저, 주어진 n에 따라 삼각형의 각 행을 초기화합니다. 이때 각 행은 i + 1개의 원소를 가집니다.

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

• 삼각형 배열 초기화: n 크기의 삼각형 배열을 초기화합니다. 이 배열은 삼각형의 각 행마다 크기가 달라지며, i번째 행은 i + 1개의 원소를 가집니다.

4. 삼각형에 숫자 채우기

삼각형을 반시계 방향으로 숫자를 채워나가는 이 과정은 크게 세 가지 방향으로 나뉩니다: 아래, 오른쪽, 대각선 위. 각 방향으로 숫자를 채운 후, 방향을 바꿔가며 삼각형을 채웁니다. 이 반복적인 과정은 삼각형이 완전히 채워질 때까지 계속됩니다.

int number = 0;  // 채워 넣을 숫자
int x = -1;      // 시작 위치 (위쪽에서 아래로 내려가기 때문에 x는 -1로 시작)
int y = 0;

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 {
            x--;  // 대각선 위로 이동
            y--;
        }
        number++;
        triangle[x][y] = number;  // 현재 위치에 숫자 채우기
    }
}

• 아래로 이동: i % 3 == 0일 때, 삼각형의 왼쪽 변을 따라 아래로 이동하며 숫자를 채웁니다. 이 단계에서는 x 좌표를 증가시켜 아래로 내려가며, y 좌표는 그대로 유지합니다. 예를 들어, (x, y)가 (0, 0)에서 시작했다면, 첫 번째 이동은 (1, 0), 그 다음은 (2, 0)로 이동하며 숫자를 채워나갑니다.
• 오른쪽으로 이동: i % 3 == 1일 때, 삼각형의 아래쪽 변을 따라 오른쪽으로 이동하며 숫자를 채웁니다. 이때는 y 좌표를 증가시켜 오른쪽으로 이동하며, x 좌표는 그대로 유지됩니다. 예를 들어, 만약 현재 위치가 (2, 0)이라면, 오른쪽으로 이동하여 (2, 1)로 이동하며 숫자를 채웁니다.
• 대각선 위로 이동: i % 3 == 2일 때, 삼각형의 오른쪽 변을 따라 대각선 위로 이동하며 숫자를 채웁니다. 이 단계에서는 x 좌표를 감소시키면서 동시에 y 좌표도 감소시킵니다. 예를 들어, 현재 위치가 (2, 2)라면, 대각선 위로 이동하여 (1, 1)로 이동하게 됩니다.

이 세 가지 방향은 삼각형의 형태와 반시계 방향의 이동 패턴을 반영합니다. 각 루프가 진행될 때마다 다음에 채워야 할 위치를 결정하는 것은 매우 중요하며, 이러한 규칙적인 좌표 변화가 문제를 해결하는 핵심입니다.

삼각형이 채워지는 과정은 이 규칙을 반복적으로 적용하여, 각 방향으로 숫자를 순차적으로 채워나가는 방식으로 이루어집니다. 이 과정을 통해 완성된 삼각형은 이후 1차원 배열로 변환되어 결과값으로 반환됩니다.

5. 1차원 배열로 변환 후 결과 반환

완성된 삼각형 배열을 1차원 배열로 변환하여 반환합니다.

int[] result = new int[number];  // 결과를 저장할 1차원 배열 생성
int index = 0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i + 1; j++) {
        result[index] = triangle[i][j];  // 삼각형 배열의 값을 1차원 배열에 복사
        index++;
    }
}

return result;  // 최종 결과 반환

󰄉 Complexity

• ⏳ TC: O(n^2)
• 💾 SC: O(n^2)

삼각형의 각 행에 대해 최대 n번의 숫자 채우기 작업을 수행하므로, 시간 복잡도는 O(n^2)입니다. 또한, 삼각형 배열을 저장하기 위해 n 크기의 2차원 배열이 필요하며, 결과 배열을 저장하기 위한 추가적인 공간도 필요하므로, 공간 복잡도 역시 O(n^2)입니다. 이 알고리즘은 삼각형의 구조와 방향성을 잘 활용하여 숫자를 체계적으로 채워나가는 방식으로 문제를 효율적으로 해결합니다.