Java 프로그래머스 - 삼각 달팽이 (Level 2)

문제 설명

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

---

문제 풀이

 

이 문제는 어떠한 알고리즘 보다는 수학적인 논리를 얼마나 잘 하느냐에 따라 달린것 같다. 처음에 어떠한 규칙을 찾으려고 노트에 이것저것 써봤는데 결국에는 조금의 힌트를 얻고 다시 풀게 되었다.

 

결국에는 이 문제 그 자체를 이해한 대로 왼쪽대각선부터 시작해서 1씩 증가 -> 가로 1씩 증가 -> 오른쪽 대각선을 위로 올라가면서 1씩 증가 를 (n*n+1)/2 까지 해주면 된다. (n*n+1)/2는 n의 값에 따른 마지막 max값이다.

 

---

 

ex) n이 4일 경우..

 

왼쪽 대각선은 i+1이 n보다 작을때까지 i만 1 증가시키면서 진행한다. ( 1-> 2-> 3 -> 4)

가로는 j+1이 n보다 작을때까지 j만 1 증가시키면서 진행한다.  ( 5->6->7 )

오른쪽 대각선은 i-1이 0보다 클때까지 ( 맨 처음에 i,j가 1,1이 될때까지) i,j모두 1씩 뺴주면서 올라간다. ( 8 -> 9 )

---

그리고 max가 아니면 다시 while문을 반복하는데 이전에 확인했던 값인지 체크하기 위해 0보다 작을 경우에만 수정해준다. 

while문이 한번 돌때마다 i와 j는 1씩 증가한 상태이다.

 

이러한 로직을 코드로 작성하면 다음과 같다.  

class Solution {
    public int[] solution(int n) {
        int max = (n * (n + 1)) / 2;
        int[][] arr = new int[n][n];
        int[] answer = new int[max];
    
        //초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                arr[i][j] = -1;
            }
        }

        int i = 0, j = 0, k = 1;
        arr[0][0] = 1;

        while (k < max) {
            while (i + 1 < n && arr[i + 1][j] < 0) { // 왼쪽 대각선
                arr[++i][j] = ++k;
            }

            while (j + 1 < n && arr[i][j + 1] < 0) { // 맨 밑 가로
                arr[i][++j] = ++k;
            }
            while (i - 1 > 0 && arr[i - 1][j - 1] < 0) { // 오른쪽 대각선
                arr[--i][--j] = ++k;
            }
            // 한바퀴 돌면 i+1,j+1 상태.=> (2,1)부터 다시 검사.
        }
        k = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j <= i; j++) {
                answer[k++] = arr[i][j];
            }
        }
        return answer;
    }
}