HackerRank [Implementation] Forming a Magic Square /알고리즘 해커랭크

문제 주소 : www.hackerrank.com/challenges/magic-square-forming/problem

난이도 : Medium
성공률 : 74.83%

 

문제 : 3x3의 입력된 배열값으로 매직스퀘어(1부터 9까지 한번씩만 사용하여 3x3 크기의 어느 방향의 세 숫자의 합을 구하더라도 15가 되는)로 수정하기 위해 발생하는 비용 구하기

 

 

풀이

1. 3x3으로 만들 수 있는 모든 매직스퀘어를 저장해 준다
2. 입력된 배열과 같은 위치(행,열)에 있는 매직스퀘어 8개와 값을 비교한다
3. 차이 값을 누적시킨 후 가장 적은 누적값을 리턴한다 

 

답안

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the formingMagicSquare function below.
def formingMagicSquare(s):

    s = sum(s, [])

    ans = [[8, 1, 6, 3, 5, 7, 4, 9, 2]
    ,[6, 1, 8, 7, 5, 3, 2, 9, 4]
    ,[4, 3, 8, 9 ,5 ,1, 2, 7, 6]    
    ,[2, 7, 6, 9, 5, 1, 4, 3, 8]
    ,[2, 9, 4, 7, 5, 3, 6, 1, 8]
    ,[4, 9, 2, 3, 5, 7, 8, 1, 6]
    ,[6, 7, 2, 1, 5, 9, 8, 3, 4]
    ,[8, 3, 4, 1, 5, 9, 6, 7, 2]
    ]

    result = []
    sumval = 0
   
    # print(s)
    for i in range(8):
        for j in range(9):
            sumval += abs(s[j]-ans[i][j])
        if sumval == 0:
            return 0  

        result.append(sumval)
        sumval = 0
        
    # print(result)    
    return min(result)


if __name__ == '__main__':
    # fptr = open(os.environ['OUTPUT_PATH'], 'w')
    fptr = sys.stdout

    s = []

    for _ in range(3):
        s.append(list(map(int, input().rstrip().split())))

    result = formingMagicSquare(s)

    fptr.write(str(result) + '\n')

    fptr.close()

 

느낀점

링크되어있는 매직블럭 위키 글을 잘 읽고 3x3의 매직블럭은 8가지 케이스가 있는걸 인지 해야만 풀 수 있었다

3x3배열에서 한 가운데에 있는 값은 항상 5이므로 테두리값의 순서가
8 1 6 7 2 9 4 3 혹은  6 1 8 3 4 9 2 7(미러버전) 인지만 확인해도 매직스퀘어인지 비교는 가능하다
다만 문제에서 요구하는 값을 추출하기에는 전체 값을 일일이  비교해봐야하기에 전체를 비교하는것이 낫다