삼각 달팽이(문제2)

25.09.14

• 삼각형을 이차원으로 표현하는걸 못떠올림
• (n)(n-1)/2 이거였나 여튼 공식이 필요했음…

import java.util.*;

class Solution {
    static int[] di = {1,0,-1};  // 아래, 오른쪽, 왼쪽위
    static int[] dj = {0,1,-1};
    static int[][] arr;
    
    public int[] solution(int n) {
        if(n==1) return new int[]{1};
        
        arr = new int[n][n];
        int total = n*(n+1)/2;  // 채워야 하는 총 개수
        int cnt = 1;
        int preI = 0, preJ = 0, dir = 0;
        arr[0][0] = 1;
        
        while(cnt < total){
            int ni = preI + di[dir];
            int nj = preJ + dj[dir];
            
            if(!isBlank(ni,nj)){   // 못 가면 방향 바꿈
                dir = (dir+1)%3;
                continue;
            }
            
            ++cnt;
            arr[ni][nj] = cnt;
            preI = ni;
            preJ = nj;
        }
        
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){   // 삼각형 부분만
                list.add(arr[i][j]);
            }
        }
        
        int[] answer = new int[list.size()];
        for(int i=0;i<list.size();i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
    
    public boolean isBlank(int i, int j){
        if(i<0 || i>=arr.length || j<0 || j>=arr.length) return false;
        if(arr[i][j] != 0) return false;
        return true;
    }
}