[LeetCode] LeetCode 1572 - matrix-diagonal-sum - Python3

최근 심심해서 리트코드 문제를 몇개 풀었는데 그 중 재밌는 문제가 몇개 있어서 정리해본다. 

 

1572번 문제이다.

 

EASY인데 첫번째 솔루션에 비해서 코드를 꽤나 효율적으로 개선해서 정리해볼 필요가 있다고 생각해서 적어둔다. 

 

일단 아래는 첫번째 제출한 솔루션이다. 꽤나 비효율적이라는걸 알 수 있다. 

 

일단 for loop 이 두개 있다는것부터 비효율적이다. 

 

'''
Runtime: 207 ms, faster than 24.29% of Python3 online submissions for Matrix Diagonal Sum.
Memory Usage: 14.1 MB, less than 57.39% of Python3 online submissions for Matrix Diagonal Sum.
'''
class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        # 0245 ~ 0250
        '''
            꽤나 흥미로운 문제였다. 그냥 직관적으로도 구현할 수 있는 문제인데
            아마 이것보다 더 쉽게 풀 수 있는 방법이 있을 것 같다.
        '''
        primary_diagonal = 0
        secondary_diagonal = 0
        for i in range(len(mat)):
            for j in range(len(mat)):
                if i == j:
                    primary_diagonal += mat[i][j]
       
        for i in range(len(mat)):
            for j in range(len(mat)):
                if i + j == (len(mat[0]) - 1):
                    secondary_diagonal += mat[i][j]
                   
        if len(mat[0]) == 1:
            return mat[0][0]
       
        if len(mat[0])%2 == 1: # 홀수라면
            return primary_diagonal + secondary_diagonal - mat[len(mat[0])//2][len(mat[0])//2]
        else:
            return primary_diagonal + secondary_diagonal

       

 

이 솔루션의 경우 굉장히 많은 진척이 있었다.

 

우선 이중 for loop이 두개 있었는데 그걸 하나로 묶었고 변수도 두개의 대각선을 사용하는게 아니라 그냥 하나의 sum 변수를 사용했다.

그리고 가장 큰 변화는 위 솔루션에서 홀수일 경우 매트릭스의 정중앙에 있는, 즉 중복해서 더해진 값을 빼주는 코드를
아래 솔루션에서는 제거했다는 것이다.

어떻게 했길래 제거해도 문제가 없을까? 

 

지금 for loop 안에 조건이 보이는가? 왼쪽 대각선, 오른쪽 대각선의 조건일 경우에 작동하는 조건문이다. 

 

그런데 이 or 로 묶인 두개의 condition에 대해 매트릭스의 정중앙은 모두 해당된다.

 

즉 중복되서 더해질 일이 아예 없다는 것이다.

 

왜냐면? 그 두개의 조건이 매트릭스의 정중앙에 모두 해당되니 각기 따로 condition에 걸릴 일이 없다는거다.

 

그러니 정중앙이 딱 한번만 condition 에 걸린다는 뜻이다.

 

그러니 중복이 없고 그러니 이후에 따로 정중앙을 빼줄 일도 없다. 

그러니 for loop을 나와서도 홀수일 경우 매트릭스의 중앙값을 굳이 빼줄 필요가 없다는 거다.

 

자 이제 아래 솔루션을 간단하게 살펴보자. 코드가 꽤 짧아진 것을 확인할 수 있다. 

 

'''
좀더 개선된 솔루션:
Runtime: 271 ms, faster than 5.04% of Python3 online submissions for Matrix Diagonal Sum.
Memory Usage: 14.1 MB, less than 57.39% of Python3 online submissions for Matrix Diagonal Sum.
'''

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        # 0245 ~ 0250
        # ~ 0303 개선
        side = len(mat[0])
        if side == 1:
            return mat[0][0]
       
        sum_of_two_diagonal= 0
        for i in range(side):
            for j in range(side):
                if (i == j) or (i + j == (side - 1)):
                    sum_of_two_diagonal += mat[i][j]

        return sum_of_two_diagonal​

 

리트코드 재밌다. 리트코드 짱