leetcode, Matrix Diagonal Sum

문제 설명

양 꼭짓점에서 이동하는 두 개의 대각선에 존재하는 숫자들을 전부 더하는 문제다. 난이도 Easy 답게 그냥 반복문으로도 풀어도 된다.

문제 풀이

첫 번째 접근

처음에는 총 두 개의 반복문을 써서 푸는 걸 생각했다. 하나는 왼쪽 위 꼭짓점에서 오른쪽 아래 꼭짓점으로 내려오는 반복문이고 또 다른 하나는 오른쪽 위 꼭짓점에서 왼쪽 아래 꼭짓점으로 내려오는 반복문이다.

이렇게 풀면 꽤 직관적이지만, 시간 복잡도는 O(n^2)이 된다. 시간을 줄이기 위해서는 반복문을 하나만 써서 푸는 방법을 알아야 한다.

두 번째 접근

시간 복잡도 O(n)으로 푸는 방법은 위의 두 반복문을 합치는 것이다. 첫 번째 접근의 첫 반복문은 그저 i와 j가 같을 때 더해주는 방식을 이용했다. 이를 그냥 i와 i로 더해줘도 된다. 그리고 두 번째 반복문에 썼던 것처럼 index를 써서 왼른쪽 위 대각선을 더해주면 된다. 이때 서로 중복되는 값을 더할 수 있으므로 만일 길이를 2로 나눈 몫이 i와 index가 같다면 answer에다가 해당 값을 빼주면 된다.

풀이

첫 번째 접근

class Solution {
    public int diagonalSum(int[][] mat) {

        int answer = 0;
        int index = mat.length-1;
        int mid = mat.length/2;
        
        for(int i=0; i<mat.length; i++){
            for(int j=0; j<mat[0].length; j++){
                if(i == j){
                    answer += mat[i][j];
                }
            }
        }

        for(int i=0; i<mat.length; i++){
            if(i == mid && index == mid){
                index--;
                continue;
            }
            answer += mat[i][index];
            index--;
        }
        
        return answer;
    }
}

두 번째 접근

class Solution {
    public int diagonalSum(int[][] mat) {

        int answer = 0;
        int index = mat.length-1;
        int mid = mat.length/2;

        for(int i=0; i<mat.length; i++){
            answer += mat[i][i] + mat[i][index];
            if(i == mid && index == mid){
                answer -= mat[i][i];
            }
            index--;
        }
        
        return answer;
    }
}