Snail, CodeWars Kata 자바 솔루션

 

Snail, CodeWars Kata

Snail Sort

Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.

array = [[1,2,3],
         [4,5,6],
         [7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]

For better understanding, please follow the numbers of the next array consecutively:

array = [[1,2,3],
         [8,9,4],
         [7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]

This image will illustrate things more clearly:

NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.

NOTE 2: The 0x0 (empty matrix) is represented as en empty array inside an array [[]].

 

n * n배열을 받아 달팽이처럼 2D 공간을 순회하면서 그 순서대로 정렬하여 1차원 배열로 반환하는 문제입니다. 사진에서 보는 것처럼 시계방향으로 바깥쪽에서부터 안쪽으로 순회하게 됩니다.

Input

• int[][]: 순회할 n*n 사이즈의 정수 배열

Output

• int[]: Snail Sort로 정렬된 1차원 배열

 

My Solution

저는 우선 규칙을 찾았습니다.

1) 우선 방향이 전환되는 횟수를 찾았습니다. 입력 배열의 3*3 이면 방향 전환 횟수는 시작을 포함해서 5번입니다. 4*4배열은 7번이고요.

2) 저는 2D배열의 인덱스를 [x][y]형태가 아니라 1차원으로 나열된 것처럼 취급하고, 방향이 전환될 때마다 가져와야 할 index에 대한 규칙을 찾았습니다. 예를 들어 3*3 배열이 입력되었을 때 [0,0], [0,1],[0,2],[1,2],[2,2]~ 순서로 진행되지만 저는 0, 1, 2, 5, 8~ 순서로 진행된다고 생각하고 진행했습니다.

달팽이처럼 순회할 때 사각형을 순회하게 되므로 진행 규칙은 4가지로 구분됩니다.

• 첫 번째 진행에서는 index가 순차적으로 1씩 증가합니다.
• 두 번째 진행에서는 index가 n만큼 늘어납니다. 3*3배열에서는 3씩 늘어 납니다.
• 세 번째 진행에서는 index가 -1만큼 줄어듭니다.
• 네 번째 진행에서는 index가 -n만큼 줄어듭니다.

3) 언제 방향을 바꿔야 할지 규칙을 찾았습니다. 3*3 배열에서는 0번째 턴에서 3만큼 진행한 후 방향을 바꿉니다. 그다음 1번째 턴에서 2만큼 진행한 후 방향을 바꿉니다. 2번째 턴에서는 마찬가지로 2만큼 진행한 후 방향을 바꿉니다. 3번째 턴에서는 1만큼 진행한 후 방향을 바꿉니다. 4번째 턴도 1만큼 진행됩니다. 이런 식으로 3*3과 4*4 배열을 관찰해 보니 n - ((turn + 1) / 2)만큼 진행하면 방향을 바꿔야 한다는 결론을 얻었습니다.

 

위와 같은 규칙을 발견한 후 작성한 코드가 아래와 같습니다.

1) 진행방향을 바꿀 때마다 증가하는 int turn 변수

2) 이번 턴에서는 얼마만큼 진행해야 하는지 알려주는 int turnAlert변수

3) 2차원 배열을 1차원처럼 다루기 위해 사용하는 int val변수

4) 루프 횟수를 기억하는 int count변수

솔루션 코드

테스트 코드

package com.codewars;

public class SnailSort {

    public static int[] snail(int[][] array) {
        int N = (array == null || array.length == 0 || array[0] == null || array[0].length == 0) ? 0 : array.length;

        int[] result = new int[N * N];

        int[] interval = new int[] { 1, N, -1, -N };
        int turn = 0;
        int val = 0;
        int count = 0;
        int turnAlert = 0;

        while (turn < (N * 2 - 1)) {
            int x = val / N;
            int y = val % N;
            result[count] = array[x][y];

            count++;
            turnAlert++;
            if (turnAlert == N - ((turn + 1) / 2)) {
                turn++;
                turnAlert = 0;
            }
            val += interval[turn % 4];
        }

        return result;
    }

}

 

Best Practice

아래 주석은 BP로 뽑힌 코드를 해석하면서 제가 달아놓은 것입니다. 아래 코드에서는 2차원 배열을 그대로 다루면서 이중 for문으로 순회합니다. 이 코드에서 제가 생각하는 두 가지 핵심 요소는 이렇습니다.

1) 바깥쪽 for의 조건 i < n / 2: 사각형 순회를 끝내고 나면 그다음 순회는 그 절반만큼의 길이로 진행됩니다.

2) 반복문 종료 후 if (n % 2 != 0) 조건문: for문의 조건이 그러하기 때문에 홀수 n*n 배열에서는 정 가운데가 남게 됩니다. 그래서 마지막 순회를 별도 처리해 줍니다.

class SnailSortBP {

    public static int[] snail(int[][] array) {
        if (array[0].length == 0)
            return new int[0];
        int n = array.length;
        int[] answer = new int[n * n];
        int index = 0;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i; j++) {
                answer[index++] = array[i][j];
                System.out.println(i + "," + j);
            } // 첫번째 루프에서 0번째 1줄을 채움

            for (int j = i + 1; j < n - i; j++) {
                answer[index++] = array[j][n - i - 1];
                System.out.println(j + "," + (n - i - 1));
            } // 두번째 루프에서 1,2 과 2,2 처리
            for (int j = i + 1; j < n - i; j++) {
                answer[index++] = array[n - i - 1][n - j - 1];
                System.out.println((n - i - 1) + "," + (n - j - 1));
            } // 세번째 루프에서는 2,1 2,0 처리
            for (int j = i + 1; j < n - i - 1; j++) {
                answer[index++] = array[n - j - 1][i];
                System.out.println((n - j - 1) + "," + (i));
            } // 마지막 루프에서는 1,0 처리
        }
        if (n % 2 != 0) { // n이 홀수이면 제일 가운데 스퀘어가 남기 때문에 별도 처리
            answer[index++] = array[n / 2][n / 2];
        }
        return answer;
    }
}