프로그래머스 코딩테스트 문제 - [Lv.2] 삼각 달팽이 (Java)

📌 문제

문제 출처 - 링크

문제 설명

정수 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]

알고리즘 분류

• 구현
• 시뮬레이션

📋 문제 요약 설명

• 그림과 같이 밑변의 길이와 높이가 n인 삼각형이 있고, 맨 꼭대기는 1개이고 아래 행으로 갈수록 하나씩 늘어난다.
• 맨 위 꼭짓점은 1이고, 꼭짓점부터 반시계 방향으로 1씩 커지며 숫자 채우기를 진행한다.
• 첫 행부터 마지막 행까지 적힌 숫자를 차례대로 새로운 배열에 넣어서 반환해라

---

💡 알고리즘 설계 / 접근 방법

1. 가로, 세로가 n인 숫자를 채울 삼각형인 배열을 만든다. (배열에는 0번 인덱스부터 값을 넣기때문에 숫자를 다 채우면 직각삼각형 모양이 된다.)

2. 삼각형의 세 변을 이동하기 위해서 계산할 때 사용할 이동 방향(아래, 오른쪽, 왼쪽 위)을 미리 선언해둔다. (아래 = 왼쪽 빗변, 왼쪽 위 = 오른쪽 빗변 그리기)

3. 2중 for문으로 높이 n만큼 순회하면서 숫자를 채운다.

   • 방향 전환용 인덱스 변수를 선언해서 모듈러 계산을 사용해 방향 정하고, 바꿔준다.
   • 아래 방향부터 시작해 숫자를 채우는데 n 횟수 만큼 채워야할 숫자 개수도 n개 이다.

4. 삼각형에 입력한 숫자 개수만큼 배열을 만들고, 2중 for문으로 삼각형을 탐색하면서 배열에 값을 넣는다.

시뮬레이션 모습

1. len=5 (↓로 5칸)

[1, 0, 0, 0, 0]
[2, 0, 0, 0, 0]
[3, 0, 0, 0, 0]
[4, 0, 0, 0, 0]
[5, 0, 0, 0, 0]

2. len=4 (→로 4칸)

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

3. len=3 (↖로 3칸)

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

4. len=2 (↓로 2칸)

[1, 0, 0, 0, 0]
[2, 12, 0, 0, 0]
[3, 13, 11, 0, 0]
[4, 14, 0, 10, 0]
[5, 6, 7, 8, 9]

5. len=1 (→로 1칸)

[1, 0, 0, 0, 0]
[2, 12, 0, 0, 0]
[3, 13, 11, 0, 0]
[4, 14, 15, 10, 0]
[5, 6, 7, 8, 9]

---

➕ 보완하기 / 성능 비교

문제에서 좌표로 이동하거나 규칙적인 방향으로 움직인다면 이동 방향을 미리 선언해두고, 좌표를 계산할 때 활용하자

---

✅ 풀이

시간 복잡도 → O(n²)

1. 삼각형 배열 채우기 : O(n²)
2. 1차원 배열로 바꿔서 채우기 : O(n²)

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[][] tri = new int[n][n];
        
        // 아래, 오른쪽, 왼쪽 위 대각선 이동 방향
        int[][] dirs = {{1, 0}, {0, 1}, {-1, -1}};
        
        int y = -1, x = 0; // 시작 좌표
        int num = 1; // 입력할 수
        int d = 0; // 방향 인덱스 (0=아래, 1=오른쪽, 2=왼쪽위)
        
        for (int len = n; len >= 1; len--) {
            // 3으로 나눈 나머지를 이용해 방향 계산
            int[] offset = dirs[d % 3];
            int dy = offset[0];
            int dx = offset[1];

            // len 횟수 만큼 수 입력하는 작업
            for (int k = 0; k < len; k++) {
                y += dy;
                x += dx;
                tri[y][x] = num++;
            }

            d++; // 다음 턴에서 사용할 방향으로 이동
        }        
        //System.out.println(Arrays.deepToString(tri));
        
        // 값 입력한 삼각형 부분만 1차원으로 평탄화
        int total = n * (n + 1) / 2; // 채울 총 개수
        
        int[] answer = new int[total];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                answer[idx++] = tri[i][j];
            }
        }
        
        return answer;
    }
}