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

programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

 

문제는 위와 같으며, 이 문제는 이차원 배열에 직접 숫자들을 위치에 맞게 저장한 뒤 최종적으로 이차원 배열에 저장된 수들 중 0이 아닌 수를 순서대로 저장하여 반환하는 방식으로 문제를 해결하였습니다.

 

예제를 통해 살펴보겠습니다. 만약 4라는 입력이 주어지는 경우 1부터 10(1 + 2 + 3 + 4)까지의 숫자를 다음과 같은 형태로 이차원 배열에 저장합니다.

 

숫자들을 하나씩 증가시키면서 위와 같은 형태로 저장할 때 다음으로 저장해야하는 인덱스는 방향성이 있습니다. 숫자를 저장할 때는 아래 그림의 화살표 순서대로 이동하며 저장이 됩니다.

 

• 1번 방향의 경우 현 위치에서 x + 1, y - 1 로 이동합니다.
• 2번 방향의 경우 현 위치에서 x, y + 1 로 이동합니다.
• 3번 방향의 경우 현 위치에서 x - 1, y - 1 로 이동합니다.

위 그림을 보면 방향을 바꿔야 하는 경우는 다음 위치가 범위 내에 포함되지 않거나 이미 0이 아닌 다른 숫자가 저장되어있는 경우이므로 조건을 확인하여 반복적으로 1~3방향을 바꿔주면서 숫자를 저장하면 됩니다.

 

정리하자면,

1. 숫자 1부터 (1 + 2 + ... + n) 까지 수를 반복하면서 숫자를 현 위치에 저장하고 (시작 위치의 경우 x = 0, y = n / 2 입니다.)

2. 방향을 이동하여 다음 위치의 x, y 를 구합니다.

3-1. 다음으로 이동할 위치가 범위 내에 포함되어 있는 경우, 현 위치를 다음 위치로 변경합니다.

3-2. 다음으로 이동할 위치가 범위 내에 포함되어 있지 않은 경우, 방향을 바꾸고 다음 위치를 다시 계산하여 현 위치를 새로 계산된 다음 위치로 변경합니다.

4. 저장할 숫자를 증가시키고 위 과정을 반복합니다.

5. 숫자를 이차원 배열에 모두 저장한 경우, 이차원 배열을 처음부터 확인하면서 0이 아닌 숫자들을 answer 배열에 담아 반환합니다.

 

자바 코드는 다음과 같습니다.

class Solution {
    private static final int[] dx = {1, 0, -1};  // x 이동 방향
    private static final int[] dy = {-1, 2, -1}; // y 이동 방향
    
    public int[] solution(int n) {
        int finalNum = getFinalNum(n); // 최종적으로 저장되어야 하는 수 구하기 n!
        int[] answer = new int[finalNum];
        int[][] matrix = new int[n][n * 2 - 1];  // 숫자들을 피라미드 형태로 저장할 이차원 배열 생성

        int setNum = 1;            // 저장할 숫자
        int sx = 0;                // 시작 위치 x
        int sy = (n * 2 - 1) / 2;  // 시작 위치 y
        int direct = 0;            // 방향 인덱스
        
        // 마지막 숫자를 저장할 때까지 반복
        while (setNum <= finalNum) {
            matrix[sx][sy] = setNum;  // 현 위치에 숫자 저장
            
            // 다음 위치 x, y 구하기
            int nx = sx + dx[direct];
            int ny = sy + dy[direct];

            // 다음으로 이동할 위치가 범위 내에 포함되어 있고 아직 다른 숫자로 채워지지 않은 경우
            if ((nx >= 0 && nx < n && ny >= 0 && ny < (n * 2 - 1)) && matrix[nx][ny] == 0) {
                // 현 위치를 다음 위치로 변경
                sx = nx;
                sy = ny;
            } else {  // 방향을 바꿔야 하는 경우
                direct = (direct + 1) % 3;  // 방향 새로 계산하기
                // 현 위치를 새로 계산된 다음 위치로 변경
                sx += dx[direct];
                sy += dy[direct];
            }
            setNum++;  // 저장할 숫자 증가
        }

        // 이차원 배열에 저장된 숫자 중 0이 아닌 숫자를 찾아 순서대로 answer 배열에 저장
        int idx = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] != 0) {
                    answer[idx] = matrix[i][j];
                    idx++;
                }
            }
        }

        return answer;
    }
    
    // n! 구하기
    private static int getFinalNum(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        return sum;
    }
}