[Programmers / Level 2] 68645. 삼각 달팽이 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68645
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/삼각 달팽이

입출력 조건

입출력 예시

문제 이해

• 삼각형의 구조적 특성을 활용해서 방향 전환을 구현하면 되는 문제

• 활용할 방법 정리

• 방향 전환 : 3가지 방향(아래, 오른쪽, 대각선 위)을 주기적으로 전환해서 채우기

• 좌표 이동 : 현재 위치(x, y)에서 방향에 따라 좌표 업데이트

• 삼각형 구조 : nxn 배열에 삼각형 패턴으로 값 저장 & 행 기준으로 읽기

알고리즘

풀이 시간 : 15분

• i % 3의 결과값에 따른 이동 방향 결정(방향 반복 횟수는 n-i번)
  • 0 : 아래로 이동(x++)
  • 1 : 오른쪽으로 이동(y++)
  • 2 : 대각선 위로 이동(x--, y--)
• 좌표 관리
  • 시작 위치 : x = -1, y = 0(첫 이동 때부터 적용)
  • 값 채우기 : num++로 1부터 할당
• 삼각형 구조에 맞게 행별로 i+1개 요소 읽기 -> 총 요소 수는 n * (n+1)/2로 계산

class Solution {
    public int[] solution(int n) {
        int total = n * (n + 1) / 2;
        int[][] matrix = new int[n][n];
        int x = -1, y = 0; // 시작 위치 (초기값)
        int num = 1; // 채울 숫자

        // 방향별 채우기
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                switch (i % 3) {
                    case 0: x++; break; // 아래
                    case 1: y++; break; // 오른쪽
                    case 2: x--; y--; break; // 대각선 위
                }
                matrix[x][y] = num++;
            }
        }
        
        int[] answer = new int[total];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                answer[idx++] = matrix[i][j];
            }
        }
        return answer;
    }
}

결과

✍️ 다른 풀이 - 1차원 배열만 사용

• 필요한 값의 총 개수를 미리 계산: n×(n+1)/2
• 현재 위치와 이동 방향을 별도 변수로 관리
• 좌표(x, y) 를 추적 -> 각 위치의 값을 1차원 배열 인덱스로 변환하여 바로 저장
• 방향 전환: 아래(0), 오른쪽(1), 대각선 위(2) 반복 -> 이건 동일

중요한 포인트

2차원 배열 없이 값이 이미 채워진 위치인지 1차원 배열에서 직접 판별

class Solution {
    public int[] solution(int n) {
        int total = n * (n + 1) / 2;
        int[] answer = new int[total];
        int[][] dir = {{1, 0}, {0, 1}, {-1, -1}}; // 아래, 오른쪽, 대각선 위
        boolean[][] visited = new boolean[n][n];
        int x = 0, y = 0, d = 0, num = 1;

        for (int i = 0; i < total; i++) {
            // 1차원 인덱스 변환: 삼각 구조이므로 행별 누적합으로 변환
            answer[getIndex(x, y)] = num++;
            visited[x][y] = true;

            int nx = x + dir[d][0];
            int ny = y + dir[d][1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) {
                d = (d + 1) % 3;
                nx = x + dir[d][0];
                ny = y + dir[d][1];
            }
            x = nx;
            y = ny;
        }
        return answer;
    }

    // (x, y) → 1차원 인덱스 변환
    private int getIndex(int x, int y) {
        return x * (x + 1) / 2 + y;
    }
}

정리

• 1차원 인덱스 : 삼각형의 (x, y) 좌표를 -> 1차원 배열 인덱스로 변환
• 2차원 visited 배열로 이미 채운 위치는 건너뜀
• 3방향을 순환하며, 갈 수 없거나 이미 방문한 경우 방향 전환하는 방식으로 사용