[프로그래머스] 삼각달팽이 - [JAVA]

https://school.programmers.co.kr/learn/courses/30/lessons/68645?language=java

프로그래머스

 

1. 정답

class Solution {
    public int[] solution(int n) {
        
        int num=n*(n+1)/2;
        
        int[][] matrix = new int[n][n];
        int c=1;
        int d=n;
        int[] state= {0,1,2};
        int x=-1, y=0;
        //0 : 아래, 1: 오른쪽 ,2 :대각선 위
        while(c<=num){
            for(int s : state){
                if(s==0){
                    for(int i=0; i<d; i++){
                        x++;
                        matrix[x][y]=c;
                        c++;
                    }
                    d--;
                    
                }
                else if(s==1){
                     for(int i=0; i<d; i++){
                        y++;
                        matrix[x][y]=c;
                        c++;
                    }
                    d--;
                    
                }
                else{
                    for(int i=0; i<d; i++){
                        x--;
                        y--;
                        matrix[x][y]=c;
                        c++;
                    }
                    d--;
                    
                }
                
            }
            
        }
        int[] answer = new int[num];
        int idx=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]!=0){
                    answer[idx++]=matrix[i][j];
                }
            }
        }
        return answer;
    }
}

 

2. 접근 

처음에는

피보나치 수열처럼 배열의 인덱스에 규칙이 있지 않을까 생각해봤는데 규칙을 못찾았다

두번째로 생각한 접근은

이렇게 방향대로 반복되는 것을 발견할 수 있었다.

방향이 바뀔때마다 n-1로 줄어들었고

이를 적용하면 쉽게 풀 수 있는 문제였다.

 

첫번째 케이스를 예로 들자면

0
1 8
2 9 7
3 4 5 6
 n=4

 

이런식으로 배열에 저장된다

그럼 방향은 3가지가 존재하는 것을 알 수 있는데 -> 아래, 오른쪽, 대각선 위의 3가지 케이스가 생긴다

 

1. 아래 방향

행이 1씩 커진다

따라서 

if(s==0){
                    for(int i=0; i<d; i++){
                        x++;
                        matrix[x][y]=c;
                        c++;
                    }
                    d--;
                    
                }

이런식으로 

행의 인덱스가 1씩 커지고 저장되는 값 c의 값도 1씩 증가한다

d를 통해 다음 방향에서 n-1만큼 배열에 저장할 수 있도록 해준다.

 

2. 오른쪽 방향

else if(s==1){
                     for(int i=0; i<d; i++){
                        y++;
                        matrix[x][y]=c;
                        c++;
                    }
                    d--;
                    
                }

열의 인덱스가 1씩 커지도록 한다

 

3. 대각선 위 방향

 else{
                    for(int i=0; i<d; i++){
                        x--;
                        y--;
                        matrix[x][y]=c;
                        c++;
                    }
                    d--;
                    
                }

행과 열이 1씩 작아진다

 

4. 출력

배열에 저장된 값 중에 0 이 아닌 값만 answer에 저장하여 return