카테고리: 배열

문제

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

풀이 방식

크기가 n인 정사각형 2차원 배열을 만들고 다음과 같이 삼각형 형태로 숫자를 채워 넣었습니다.

반복되는 사이클은 1.아래로 이동하기, 2. 오른쪽으로 이동하기, 3.대각선으로 이동하기 입니다.
위치는 (x,y)로 두고, x와 y의 위치 변화량을 dx와 dy로 정의합니다.

1. dx, dy 정의

private static final int[] dx = {0, 1, -1};
private static final int[] dy = {1, 0 ,-1};

2. 변수 초기화

int[][] snail = new int[n][n]; 

int x = 0;
int y = 0;
int cycle = 0;
int num = 1;

3. 종료 조건에 도달할 때까지 반복문 실행

while(true){
 	snail[y][x] = num++;

	int next_x = x + dx[cycle];
    int next_y = y + dy[cycle];
    //한 사이클 종료 조건
    if(next_x == n || next_x == -1 || next_y == n || next_y == -1 || snail[next_y][next_x] != 0){
    	cycle = (cycle + 1 ) % 3;
        next_x = x + dx[cycle];
        next_y = y + dy[cycle];
        //완전 종료 조건 (더 이상 이동할 수 없을 때)
        if(next_x == n || next_x == -1 || next_y == n || next_y == -1 || snail[next_y][next_x] != 0) break;
    }
        
    x = next_x;
    y = next_y;
}	

최종 코드

class Solution {
    private static final int[] dx = {0, 1, -1};
    private static final int[] dy = {1, 0 ,-1};
    public int[] solution(int n) {
        int[][] snail = new int[n][n];

        int x = 0;
        int y = 0;
        int cycle = 0;
        int num = 1;

        while(true){
            snail[y][x] = num++;

            int next_x = x + dx[cycle];
            int next_y = y + dy[cycle];
            //한 사이클 종료 조건
            if(next_x == n || next_x == -1 || next_y == n || next_y == -1 || snail[next_y][next_x] != 0){
                cycle = (cycle + 1 ) % 3;
                next_x = x + dx[cycle];
                next_y = y + dy[cycle];
                //완전 종료 조건
                if(next_x == n || next_x == -1 || next_y == n || next_y == -1 || snail[next_y][next_x] != 0) break;
            }
            x = next_x;
            y = next_y;
        }

        int[] result = new int[num-1];
        int index = 0;
        for(int[] arr : snail){
            for(int number :  arr){
                if(number != 0) result[index++] = number;
            }
        }

        return result;
    }
}