[HackerRank] 2D Array - DS

문제 풀이:)

2차원 배열에서 나올 수 있는 모든 모래시계를 구한 다음에 그 모래시계의 합의 최댓값을 구하면 되는 문제다.

모래시계를 어떻게 구할 수 있을까?

 

시작 좌표가 0부터 시작한다고 하면 다음과 같이 모래시계를 구할 수 있다.

(0,0) (0,1) (0,2)
      (1,1)
(2,0) (2,1) (2,2)

2차원 배열에서 나올 수 있는 모든 모래시계는 어떻게 찾을 수 있을까?

 

하나의 좌표를 기준으로 확인해보면 된다.

여기서 하나의 좌표를 기준은 모래시계의 최상단 왼쪽 배열인 (0,0)을 기준으로 확인하면 된다.

만약에 6 x 6 배열에서 찾고자 한다면 범위는

열로 보면 0 ~ 3까지만,

행로 보면 0 ~ 3까지만,

탐색하면 된다.

 

만약에 4를 보면?

(0,4) (0,5) (0,6)
      (1,5)
(2,4) (2,5) (2,6)

이미 인덱스를 넘어서게 된다.

 

이러한 범위만 주의해서 코드를 짜면 문제를 해결할 수 있다.

int hourglassSum(vector<vector<int>> arr) {
    int ans = -987654321;
    int row = arr.size();
    int col = arr[0].size();
    for(int i = 0; i < row - 2; i++) {
        for(int j = 0; j < col - 2; j++) {
            int sum = 0;
            sum += arr[i][j] + arr[i][j+1] + arr[i][j+2];
            sum += arr[i+1][j+1];
            sum += arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2];
            ans = max(ans, sum);
        }
    }
    return ans;
}