[Leetcode] #1572. Matrix Diagonal Sum 매트릭스 대각선에 위치한 수들의 합

문제 요약

자세한 내용은 leetcode에서 확인

https://leetcode.com/problems/matrix-diagonal-sum/

nxn 2d 배열의 대각선에 위치한 수들의 합을 찾아라.

예제

input: 

[[1, 2, 3],

 [4, 5, 6],

 [7, 8, 9]]

output: 25

풀이

2 포인터 문제

하나는 맨 왼쪽부터, 다른 하나는 맨 오른쪽부터 시작하여 1씩 증가/감소. n이 홀수라면 두 포인터가 정 가운데에서 만나는데 이때 한번만 카운트하는것이 중요 포인트.

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

int sum = 0;

// 왼쪽 위에서 오른쪽 아래로 이동하는 포인터

int lToR = 0;

// 오른쪽 위에서 왼쪽 아래로 이동하는 포인터

int rToL = mat[0].length - 1;

for (int i=0; i<mat.length; i++) {

sum += mat[i][lToR];

// 만약 두개의 포인터가 다른곳을 가리킬 때에만 두번째 값을 더한다

if (lToR != rToL) {

sum += mat[i][rToL];

}

// 오른쪽으로 한 칸 이동

lToR++;

// 왼쪽으로 한 칸 이동

rToL--;

}

return sum;

}

Complexity

time: O(n) - n 노드 갯수 만큼 for loop을 돈다.

space: O(1) - 몇개 안되는 변수를 생성하였다.