HackerRank [Constructive Algorithms] Flipping the Matrix /알고리즘 해커랭크

문제주소 : www.hackerrank.com/challenges/flipping-the-matrix/problem

 

문제 : 2n * 2n 크기의 매트릭스를 큐브돌리듯이 상하 좌우를 회전시켜서 n * n 크기의 좌측상단 매트릭스에 최대값이 위치하도록 한 뒤 그 매트릭스의 모든값을 합한값을 리턴하라

 

풀이

1. 매트릭스 가장 좌측상단의 1열1행에 있는 값은 아무리 회전한들 결국 존재할 수 있는 위치는 n열n행, 1열 n행, n열 1행, 1열1행 4곳밖에 존재 할 수 없다 
2. 반대로 그 4곳에 위치하는 값중 가장 큰 값이 1열1행에 존재하게 될 것이다
3. 모든 나머지 매트릭스의 위치값들도 matrix[i][j], matrix[i][n-j-1], matrix[n-i-1][j], matrix[n-i-1][n-j-1] 이 4개의 값 중 가장 큰 값이 좌측상단에 오게되고 그 값의 합을 구하면 된다

 

답안

import math
import os
import random
import re
import sys

def flippingMatrix(matrix):
    n = len(matrix)
    s = 0
    for i in range(n//2):
        for j in range(n//2):
            s += max(matrix[i][j], matrix[i][n-j-1], matrix[n-i-1][j], matrix[n-i-1][n-j-1])
    return s

def flipping(matrix, nLen, bCol, nCnt): # 뒤집기 사용안함
    if bCol == True:
        for i in range(int(nLen/2)):
            nTemp = matrix[i][nCnt]
            matrix[i][nCnt] = matrix[nLen-i-1][nCnt]
            matrix[nLen-i-1][nCnt] = nTemp
  
    else:
        for i in range(int(nLen/2)):
            nTemp = matrix[nCnt][i]
            matrix[nCnt][i] = matrix[nCnt][nLen-i-1]
            matrix[nCnt][nLen-i-1] = nTemp                  
    
    return matrix

def flippingMatrix2(matrix):  #사용안함
    nLen = len(matrix)    

    while(True):        
        bClearC = True
        bClearR = True
        lMax = [0,0]        
       
        for i in range(nLen):            
            nSum = 0
            for j in range(nLen):                
                if j < nLen/2:
                    nSum += matrix[j][i]                    
                else:
                    nSum -= matrix[j][i] 
            if nSum < lMax[0]:
                lMax[0] = nSum
                lMax[1] = i
                bClearC = False
        
        if bClearC == False:
            flipping(matrix, nLen, True, lMax[1])

        lMax = [0,0]
        for i in range(nLen):   
            nSum = 0        
            for j in range(nLen):
                if j < nLen/2:
                    nSum += matrix[i][j]                    
                else:
                    nSum -= matrix[i][j] 
            if nSum < lMax[0]:
                lMax[0] = nSum
                lMax[1] = i
                bClearR = False                

        if bClearR == False:
            flipping(matrix, nLen, False, lMax[1])                

        if (bClearC and bClearR):
            nSumVal = 0
            for i in range(int(nLen/2)): 
                for j in range(int(nLen/2)):
                    nSumVal += matrix[i][j]
            return nSumVal



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

    q = int(input())

    for q_itr in range(q):
        n = int(input())

        matrix = []

        for _ in range(2*n):
            matrix.append(list(map(int, input().rstrip().split())))

        result = flippingMatrix(matrix)

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

    fptr.close()

 

느낀점

처음엔 실제로 뒤집는 역할을 하는 함수를 만들고 처음 뒤집었을때 가운데를 기점으로 각각 (예를들면 좌측vs우측 혹은 상단vs하단) 스왑되는 값의 합을 비교하여 스왑하면 가장 큰 이득을 보는 동작이 뭔지 확인 하고 그 작업을 계속 반복하였다 (flippingmatrix2) 
그 결과 예제2개는 통과하였으나 나머지 모든예제에서 예외 에러가 발생했다

알고리즘을 잘 만드는것 보다 작성하기 전 어떻게 효율적으로 작성해야 하는지 고민이 더 중요했던 문제