[C++] HackerRank 해커랭크 2D Array - DS 풀이

발상의 전환만 하면 쉽게 풀 수 있는 문제

 

---

문제의 조건

1. 2차원 배열이 주어지는데 

---

ㅣ

---

처럼 모래시계 모양 위치에 있는 요소들의 합 중 최대값을 구하기 

---

 

여러 방법이 있겠지만 모래시계의 가운데 한 칸을 중심점으로 잡고 2중 반복문을 돌리면 쉽게 구할 수 있습니다. 

배열의 크기는 6x6으로 고정이라 타임아웃 걱정은 안 해도 됩니다. 

 

int hourglassSum(vector<vector<int>> arr) {

    //배열 요소의 값 범위가 -9 ~ 9 까지라 최소값이 음수도 나올 수 있다.
    //7개의 합을 구해야 하기 때문에 -9*7=-63
    int iHourGlassSum = -63;
    
    for (int i = 1; arr.size() - 1 > i; i++)
    {
        for (int j = 1; arr[i].size() - 1 > j; j++)
        {
            //모래시계의 가운데 점을 기준으로 윗줄 세칸, 가운데, 아랫줄 세칸을 임시변수에 더해준 뒤
            int iTmp = 0;
            iTmp += arr[i-1][j-1];
            iTmp += arr[i-1][j];
            iTmp += arr[i-1][j+1];
            iTmp += arr[i][j];
            iTmp += arr[i+1][j-1];
            iTmp += arr[i+1][j];
            iTmp += arr[i+1][j+1];
            
            //더 큰 값을 저장하기 
            //반복문이 끝나면 가장 큰 값이 저장 되어 있을 것이다. 
            iHourGlassSum = max(iHourGlassSum, iTmp);
        }
    }
    
    return iHourGlassSum;
}

 

휴...

쉬운 문제였지만 처음에는 감이 안 와서 힌트가 필요했던 문제 

저도 알고리즘 문제 보자마자 각이 서서 술술 풀었으면 좋겠네요.