[해커랭크] Forming a Magic Square

[해커랭크] Forming a Magic Square

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

You will be given a matrix of integers in the inclusive range . We can convert any digit to any other digit in the range at cost of . Given , 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 .

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 .

Function Description

Complete the formingMagicSquare function in the editor below.

formingMagicSquare has the following parameter(s):

• int s[3][3]: a array of integers

Returns

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

Input Format

Each of the lines contains three space-separated integers of row .

Constraints

•  

Sample Input 0

4 9 2
3 5 7
8 1 5

Sample Output 0

1

Explanation 0

If we change the bottom right value, , from to at a cost of , 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

• -> at a cost of
• -> at a cost of
• -> at a cost of ,

then the total cost will be .

 

 

 

 

 

 

 

풀이

재귀와 백트래킹을 활용한 브루트포스 알고리즘 방식으로 풀어보았다

모든 가능한 순열을 만들면서, 매직스퀘어인지 체크해보고, 모든 가능한 매직스퀘어를 만들어둔다.

입력값인 s와 내가 만든 모든 매직스퀘어를 비교하면서 최소비용을 구해버린다

 

말이야 쉬웠지 은근히 손이 많이갔다

미디움 웰던인 녀석이었다

 

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

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 boolean isMagic(List<Integer> nums){

        for (int i = 0; i < 3; i++) {

            int rowSum = 0;

            int colSum = 0;

           

            for (int j = 0; j < 3; j++) {

                rowSum += nums.get((i*3) + j);

                colSum += nums.get((j*3) + i);

            }

            if (rowSum != 15 || colSum != 15){

                return false;

            }

           

           

        }

        int rightDownSum = nums.get(0) + nums.get(4) + nums.get(8);

        int rightUpSum = nums.get(2) + nums.get(4) + nums.get(6);

       

        return (rightDownSum == 15 && rightUpSum == 15) ? true : false;

    }

     

    public static void  generateMagicSquare(List<Integer> nums, int swapIndex, List<List<Integer>> magicSquareList) {

       

         if (swapIndex == nums.size()) {    // change complete

            if (isMagic(nums)) {

                magicSquareList.add(new ArrayList<>(nums));

            }

            return;

        }

       

        for(int i=swapIndex; i<nums.size(); i++){

            Collections.swap(nums, i, swapIndex);   // change i and index

            generateMagicSquare(nums, swapIndex+1, magicSquareList);

            Collections.swap(nums, i, swapIndex);   // revert

        }

    }

    public static int formingMagicSquare(List<List<Integer>> s) {

    // Write your code here

        List<Integer> oneToNine = Arrays.asList(1,2,3,4,5,6,7,8,9);

        List<List<Integer>> magicSquareList = new ArrayList<>();

        int tempIndex = 0;

        generateMagicSquare(oneToNine, tempIndex, magicSquareList);

       

        int minCost = Integer.MAX_VALUE;

        for(List<Integer> nine : magicSquareList){

            int tempSumCost = 0;

            for(int i=0; i<9; i++){

                int n = nine.get(i);

                int origin = s.get(i/3).get(i%3);

                tempSumCost += Math.abs(n-origin);

            }

            minCost = (tempSumCost < minCost) ? tempSumCost : minCost;

           

        }

        return minCost;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        List<List<Integer>> s = new ArrayList<>();

        IntStream.range(0, 3).forEach(i -> {

            try {

                s.add(

                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

                        .map(Integer::parseInt)

                        .collect(toList())

                );

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

        });

        int result = Result.formingMagicSquare(s);

        bufferedWriter.write(String.valueOf(result));

        bufferedWriter.newLine();

        bufferedReader.close();

        bufferedWriter.close();

    }

}