[Java] Forming a Macig Square - HackerRank Algorithms

문제 링크

Forming a Magic Square | HackerRank

 

 

문제 설명

어떤 이차원배열이 들어왔을 때, 최소 cost로 마방진을 완성시키고, cost를 출력하는 문제

 

마방진이란 n^2개의 수를 가로 세로, 대각선 방향의 수를 더하면 모두 같은 수가 나오도록 n x n 행렬에 배열한 것을 말한다 ( 위키백과 )

 

 

 

풀이를 위한 참조

마방진 - 위키백과, 우리 모두의 백과사전

 

위키백과를 살펴보면, 아래의 그림처럼 마방진을 만들 수 있는 방법을 서술해 놓았다.

 

 

 

 

풀이

문제에서 n은 3으로 고정되어 있기 때문에, 조금 더 명확하게 문제를 접근할 수 있었다. 굳이 위키백과에서 나온 것 처럼 홀수 차수의 마방진을 만드는 방법을 100% 활용하지는 않았고, 규칙성을 찾아서 접근하였다.

 

 

규칙

3x3 배열에서의 마방진은, 중앙의 수([1][1])가 5로 고정되어야만 하고, 대각선의 값이 항상 4,6으로 고정되어야 한다.

 

위의 규칙을 기준으로, 대각선의 값이 항상 4, 6으로 고정되어야 할 때, 3x3배열에서의 마방진은 총 8가지 경우가 존재한다.

 

이를 활용하여 내가 작성한 코드는 아래와 같다.

public static int formingMagicSquare(List<List<Integer>> s) {
    int[][][] magicSquares = {
        {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
        {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
        {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
        {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},
        {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},
        {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},
        {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},
        {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}
    };

    int answer = Integer.MAX_VALUE;

    for (int[][] magicSquare : magicSquares) {
        int cost = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cost += Math.abs(magicSquare[i][j] - s.get(i).get(j));
            }
        }
        answer = Math.min(answer, cost);
    }

    return answer;
}

 

8가지 경우의 마방진을 이차원 배열에 담았고, 입력 받는 s와 비교해서, 가장 작은 cost를 구했다.

 

HackerRank의 문제를 처음 풀어보았는데, 문제 자체가 어렵지는 않았다. 물론 어려운 문제도 많이 있겠지만 적응을 위해 적당한 난이도를 선정했다.

 

코딩 문제를 풀 때, 프로그래머스나 LeetCode만 참조했고 백준과에 속하는(?) I/O를 고려해야하는 문제를 풀어보지 않았기 때문에, 조금 적응하는 데 시간이 필요한 것 같다.