프로그래머스(삼각 달팽이)-구현

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

1. 걸린 시간

40분

2. 트리거

삼각형 또한 y와 x좌표로 나타낼 수 있다.

그리고 이를 일차원 배열로 나타냈을 때, 식은

 int index = ( (y * (y + 1)) / 2 + x); => y = 0부터 시작 x = 0부터 시작

와 같다.

이를 n을 기준으로 3개씩 줄어드는 삼각형의 특성을 고려해 n-3 재귀를 했다.

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[] answer = solve(n);    
        return answer;
    }
    
    private int[] solve(int n) {
        int[] answer = new int[(n * (n+1)) / 2];
        fillTriple(answer, n, 0, 0, 1);
        return answer;
    }
    
    private void fillTriple(int[] answer, int n, int sy, int sx, int startNum) {
        if(n <= 0) return;
        if(n == 1) {
            int index = ( (sy * (sy + 1)) / 2 + sx);
            answer[index] = startNum++;
            return;
        }
        
        int cy = sy;
        int cx = sx;
        while(cy < sy + n - 1) {
            int index = ( (cy * (cy + 1)) / 2 + cx);
            answer[index] = startNum++;
            cy++;
        }
        
        while(cx < sx + n - 1) {
            int index = ( (cy * (cy + 1)) / 2 + cx);
            answer[index] = startNum++;
            cx++;
        }
        
        while(cy > sy && cx > sx) {
            int index = ( (cy * (cy + 1)) / 2 + cx);
            answer[index] = startNum++;
            cy--;
            cx--;
        }
        cy++;
        cx++;
    
        fillTriple(answer, n - 3, cy + 1, cx, startNum);
    }
}