[PG] 삼각 달팽이 JAVA

programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

문제 설명

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

---

제한사항

• n은 1 이상 1,000 이하입니다.

---

입출력 예

nresult

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]

 

 

 

 

 

 

 

풀이 .

class Solution {
    public int[] solution(int n) {
        int max = 0;
        for(int i = 1; i <= n; i++) {
            max += i;
        }
        int[] answer = new int[max];
        int[][] arr = new int[n][n];

        int row = 0, col = 0, input = 1;
        arr[row][col] = input;
        while(input < max) {
            // 상 -> 하 (row++)
            while(row + 1 < n && arr[row+1][col] == 0) {
                arr[++row][col] = ++input;
            }
            // 좌 -> 우 (col++)
            while(col + 1 < n && arr[row][col+1] == 0) {
                arr[row][++col] = ++input;
            }
            // 우하 -> 좌상 (row--, col--)
            while(row - 1 > 0 && col - 1 > 0 && arr[row-1][col-1] == 0) {
                arr[--row][--col] = ++input;
            }
        }

        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                answer[idx++] = arr[i][j];
            }
        }
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
    }
}

 

이차원 배열로 삼각형을 표현할 수 있다.

(대각선을 그었을 때 아래쪽 삼각형에 해당하는 좌표만 사용)

 

문제의 경우에서 이동할 수 있는 방향은 총 세 가지.

1. 위쪽에서 아래쪽으로 수직 이동

2. 왼쪽에서 오른쪽으로 수평 이동

3. 오른쪽 아래에서 왼쪽 위로 대각 이동

 

각 경우에 대한 while()문을 만들어 준다.

 

처음에는 이전 좌표의 값에 +1을 해주려고 했었는데 이렇게 하려니 이동 방향을 꺾을 때마다 이전 좌표 값을 다르게 찾아야 하는 방식이 까다로웠다.

 

배열에 할당하는 최대 숫자 max를 먼저 구하고 input : 1 ~ max 를 할당하도록 하여 이 문제를 해결했다.