[HackerRank, python, Medium] Forming a Magic Square
문제
3x3
행렬이 주어지고 이를 마방진으로 바꾸기 위한
최소 비용을 리턴하는 문제이다.
마방진 : 모든 행,열,대각선의 합이 같은 행렬
예시
주어진 행렬
5 3 4
1 5 8
6 4 2
마방진으로 수정
8 3 4
1 5 9
6 7 2
바뀐 숫자
5
-> 8
8
-> 9
4
-> 7
비용 : | 5-8 | + | 8-9 | + | 4-7 | = 7 |
풀이
3x3
마방진은 총 8개의 경우 밖에 없다.
6 1 8 6 7 2 2 9 4 8 3 4
7 5 3 1 5 9 7 5 3 1 5 9
2 9 4 8 3 4 6 1 8 6 7 2
4 9 2 4 3 8 2 7 6 8 1 6
3 5 7 9 5 1 9 5 1 3 5 7
8 1 6 2 7 6 4 3 8 4 9 2
이를 전부 배열로 만든다.
all_magics = [
[[6,1,8],[7,5,3],[2,9,4]],
[[6,7,2],[1,5,9],[8,3,4]],
[[2,9,4],[7,5,3],[6,1,8]],
[[8,3,4],[1,5,9],[6,7,2]],
[[4,9,2],[3,5,7],[8,1,6]],
[[4,3,8],[9,5,1],[2,7,6]],
[[2,7,6],[9,5,1],[4,3,8]],
[[8,1,6],[3,5,7],[4,9,2]],
]
주어진 행렬과 위 8가지 행렬의 비용을 전부 계산한다.
list_cost = [0,0,0,0,0,0,0,0]
for i in range(8):
for j in range(3) :
list_cost[i] += abs(all_magics[i][j][0]-s[j][0])
list_cost[i] += abs(all_magics[i][j][1]-s[j][1])
list_cost[i] += abs(all_magics[i][j][2]-s[j][2])
가장 낮은 비용을 리턴한다.
return min(list_cost)
전체코드
def formingMagicSquare(s):
all_magics = [
[[6,1,8],[7,5,3],[2,9,4]],
[[6,7,2],[1,5,9],[8,3,4]],
[[2,9,4],[7,5,3],[6,1,8]],
[[8,3,4],[1,5,9],[6,7,2]],
[[4,9,2],[3,5,7],[8,1,6]],
[[4,3,8],[9,5,1],[2,7,6]],
[[2,7,6],[9,5,1],[4,3,8]],
[[8,1,6],[3,5,7],[4,9,2]],
]
list_cost = [0,0,0,0,0,0,0,0]
for i in range(8):
for j in range(3) :
list_cost[i] += abs(all_magics[i][j][0]-s[j][0])
list_cost[i] += abs(all_magics[i][j][1]-s[j][1])
list_cost[i] += abs(all_magics[i][j][2]-s[j][2])
return min(list_cost)
Leave a comment