[HackerRank] Forming a Magic Square JAVA

🔗 HackerRank Forming a Magic Square https://www.hackerrank.com/challenges/magic-square-forming/problem?isFullScreen=true

문제

We define a magic square to be an n x n matrix of distinct positive integers from 1 to n² where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.

 

You will be given a 3 x 3 matrix s of integers in the inclusive range [1,9]. We can convert any digit a to any other digit b in the range [1,9] at cost of |a-b|. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.

 

Note : The resulting magic square must contain distinct integers in the inclusive range [1,9].

 

Example

 

$s = [[5,3,4], [1,5,8], [6,4,2]]

 

The matrix looks like this:

5 3 4
1 5 8
6 4 2

We can convert it to the following magic square:

8 3 4
1 5 9
6 7 2

This took three replacements at a cost of |5-8| + |8-9| + |4-7| = 7

 

Function Description

 

Complete the formingMagicSquare function in the editor below.

formingMagicSquare has the following parameter(s):

- int s[3][3]: a 3 x 3 array of integers

 

Returns

- int: the minimal total cost of converting the input square to a magic square

 

Input Format

Each of the 3 lines contains three space-separeted integers of row s[i].

 

Constraints

- s[i][j] ∈ [1,9]

 

Sample Input 0

4 9 2
3 5 7
8 1 5

 

Sample Output 0

1

 

Explanation 0

If we change the bottom rigth value, s[2][2], from 5 to 6 at a cost of |6-5| = 1, s becomes a magic square at the minimum possible cost.

 

Sample Input 1

4 8 2
4 5 7
6 1 6

 

Sample Output 1

4

 

Explanation 1

Using 0-based indexing, if we make

- s[0][1]->9 at a cost of |9-8| = 1

- s[1][0]->3 at a cost of |3-4| = 1

- s[2][0]->8 at a cost of|8-6| = 2

then the total cost will be 1+1+2 = 4.

 

🔻번역

우리는 임의의 행, 열 또는 길이 n의 대각선의 합이 항상 동일한 숫자인 1에서 n²까지 구별되는 양의 정수 n × n 행렬의 마방진을 정의하려고 합니다.

 

[1, 9] 범위의 정수 행렬 3 × 3 이 주어집니다.

우리는 |a - b| 의 결과로 임의의 숫자 a 를 [1, 9] 범위의 다른 숫자 b로 변환할 수 있습니다.

s 가 주어진 경우, 최소값으로 마방진을 변환하십시오.

이 최소값을 출력시키시오.

 

참고 : 마방진의 결과값에는 [1, 9] 범위에 포함되는 고유한 정수여야 합니다.

 

Example

 

$s = [[5,3,4], [1,5,8], [6,4,2]]

 

행렬은 다음과 같습니다.

5 3 4
1 5 8
6 4 2

다음과 같은 마방진으로 변환할 수 있습니다.

8 3 4
1 5 9
6 7 2

 이 변환은 세번의 교체로 |5-8| + |8-9| + |4-7| = 7 와 같은 값을 가집니다.

 

Function Description

 

다음 편집기에서 formingMagincSquare 함수를 완성시킵니다.

formingMaginSquare는 다음과 같은 매개변수를 가집니다.

- int s[3][3]: int타입 3 x 3 배열  

 

Returns

 

- int: 입력된 사각형을 마방진으로 변환하는 최소값

 

Input Format

 

s[i]의 세 줄에는 각각 3개의 공백으로 구분된 정수가 포함되어 있습니다.

 

Constraints

 

- s[i][j] ∈ [1,9]

 

Sample Input 0

4 9 2
3 5 7
8 1 5

 

Sample Output 0

1

 

Explanation 0

우측 하단 값인 s[2][2]를 5에서 6으로 변경하게 되면 |5 - 6| = 1의 값으로 s는 최소값의 변경으로 마방진이 된다.

 

Sample Input 1

4 8 2
4 5 7
6 1 6

 

Sample Output 1

4

 

Explanation 1

0 기반 인덱싱

 

- s[0][1] -> 9 변경 시 |9 - 8| = 1 

- s[1][0] -> 3 변경 시 |3 - 4| = 1

- s[2][0] -> 8 변경 시 |8 - 6| = 2

즉, 총 비용은 1 + 1 + 2 = 4 가 된다.

---

풀이

마방진을 처음 봐서 매우 어려웠다.

일단 마방진에는 규칙이 존재했다.

 

3×3 마방진 규칙

1. 가운데에는 5가 고정된다.

2. 각 모서리에는 [2, 4, 6, 8] 짝수만이 들어간다.

3. 그 외에는 홀수만 들어간다.

4. 각 가로의 합, 세로의 합, 대각선의 합이 15이다.

 

마방진을 처음 보니 어떻게 해결해야 할지 모르겠기에 나는 만들 수 있는 경우의 수를 모두 구해준 후, 절대값을 구해서 가장 작은 수를 반환시켜주었다.

하지만 이런 방법으로 풀면 안될 듯 싶어 레퍼런스를 보았더니 역시나,,,, 너무 무지성인 풀이였다.

 

내가 푼 코드 (무지성)

class Result {

    /*
     * Complete the 'formingMagicSquare' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY s as parameter.
     */

    public static int formingMagicSquare(List<List<Integer>> s) {
    // Write your code here
        int [] ans = new int[8];
        int [][] magic1 = {{8,1,6},{3,5,7},{4,9,2}};
        int [][] magic2 = {{8,3,4},{1,5,9},{6,7,2}};
        int [][] magic3 = {{6,1,8},{7,5,3},{2,9,4}};
        int [][] magic4 = {{6,7,2},{1,5,9},{8,3,4}};
        int [][] magic5 = {{4,3,8},{9,5,1},{2,7,6}};
        int [][] magic6 = {{4,9,2},{3,5,7},{8,1,6}};
        int [][] magic7 = {{2,7,6},{9,5,1},{4,3,8}};
        int [][] magic8 = {{2,9,4},{7,5,3},{6,1,8}};
        
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                ans[0] += Math.abs(s.get(i).get(j) - magic1[i][j]);
                ans[1] += Math.abs(s.get(i).get(j) - magic2[i][j]);
                ans[2] += Math.abs(s.get(i).get(j) - magic3[i][j]);
                ans[3] += Math.abs(s.get(i).get(j) - magic4[i][j]);
                ans[4] += Math.abs(s.get(i).get(j) - magic5[i][j]);
                ans[5] += Math.abs(s.get(i).get(j) - magic6[i][j]);
                ans[6] += Math.abs(s.get(i).get(j) - magic7[i][j]);
                ans[7] += Math.abs(s.get(i).get(j) - magic8[i][j]);
            }
        }
        Arrays.sort(ans);
        return ans[0];
    }

}

 

레퍼런스를 보며 이해해보니 경우의 수라는 점을 간과하였다.

경우의 수는 재귀(dfs)를 통해 구현할 수 있었다.

 

레퍼런스의 시점과 현 문제가 살짝 변경되어 그에 맞게 변경한 코드와 출처를 링크하도록 하겠다.

 

🔻레퍼런스 코드

class Result {

    /*
     * Complete the 'formingMagicSquare' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY s as parameter.
     */

    public static int formingMagicSquare(List<List<Integer>> s) {
        // Write your code here
        // 3x3 마방진
        // 8 1 6
        // 3 5 7
        // 4 9 2
        int min = 72;
        List<List<Integer>> magicSquare = makeMagicSquare();

        for (List<Integer> square : magicSquare) {
            int cost = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    cost += Math.abs(s.get(i).get(j) - square.remove(0));
                }
            }
            if(cost < min) min = cost;
        }
        return min;
    }

    static List<List<Integer>> makeMagicSquare() {
        // 가운데 5 고정, 8개의 숫자순열
        int[] arr = {1, 2, 3, 4, 6, 7, 8, 9};
        List<List<Integer>> permList = new ArrayList<>();
        perm(permList, arr, 0);

        for (List<Integer> a : permList) a.add(4, 5);

        // 각 가로 합, 세로 합, 대각선 합이 15인 행렬만 저장할 리스트트
       List<List<Integer>> magicSquare = new ArrayList<>();

        for (List<Integer> a : permList) {
            if ((a.get(0) + a.get(1) + a.get(2)) == 15 &&
                    (a.get(3) + a.get(4) + a.get(5)) == 15 &&
                    (a.get(6) + a.get(7) + a.get(8)) == 15 &&
                    (a.get(0) + a.get(3) + a.get(6)) == 15 &&
                    (a.get(1) + a.get(4) + a.get(7)) == 15 &&
                    (a.get(2) + a.get(5) + a.get(8)) == 15 &&
                    (a.get(0) + a.get(4) + a.get(8)) == 15 &&
                    (a.get(2) + a.get(4) + a.get(6)) == 15) {
                magicSquare.add(a);
            }
        }
        return magicSquare;
    }

    /**
     * 홀수 마방진 규칙
     * 4개의 모서리 : {2, 4, 6, 8}
     * 가운데 : {5}
     * 그 외 : {1, 3, 5, 7}
     *
     * 가운데 5를 고정으로 {1, 2, 3, 4, 6, 7, 8, 9} 조합으로 나올 행렬의 개수 = 8!
     */
    static void perm(List<List<Integer>> permList, int[] arr, int pivot) {
        if (pivot == arr.length) {
            List<Integer> a = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) a.add(arr[i]);
            permList.add(a);
            return;
        }
        for (int i = pivot; i < arr.length; i++) {
            swap(arr, i, pivot);
            perm(permList, arr, pivot + 1);
            swap(arr, i, pivot);
        }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

레퍼런스 블로그
https://ejiaah.com/algorithm/hackerrank/hackerrank-Forming-a-Magic-Square/