[해커랭크(HackerRank)] - 3D Surface Area

[문제 링크]

https://www.hackerrank.com/challenges/3d-surface-area/problem

 

[함수부 구현(C++)]

int surfaceArea(vector<vector<int>> A) {
    int front, back, right, left;
    int calc;
    front = back = right = left = 0;

    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < A[i].size(); j++) {
            if (j == 0)                    front += A[i][j];
            if (j == A[i].size() - 1)    back += A[i][j];
            if (i == 0)                    right += A[i][j];
            if (i == A.size() - 1)        left += A[i][j];

            if (j + 1 < A[i].size()) {
                calc = A[i][j] - A[i][j + 1];
                if (calc < 0) {
                    front += (calc * -1);
                }
            }
            if (j - 1 >= 0) {
                calc = A[i][j] - A[i][j - 1];
                if (calc < 0) {
                    back += (calc * -1);
                }
            }
            if (i + 1 < A.size()) {
                calc = A[i][j] - A[i + 1][j];
                if (calc < 0) {
                    right += (calc * -1);
                }
            }
            if (i - 1 >= 0) {
                calc = A[i][j] - A[i - 1][j];
                if (calc < 0) {
                    left += (calc * -1);
                }
            }

        }
    }

    return front + back + right + left + ((A.size() * A[0].size()) * 2);
}

 

[내용]

1*1 작은 블록을 여러개 쌓았을 때 n*m 다면체가 각각의 면이 바깥으로 향하는 작은 블록의 면의 수를 출력하는 문제

 

처음에 3D 블록이 나와서 겁먹었지만 차근차근 고민해보면 많이 어려운 문제는 아니였다

3D 블록이니깐 바깥으로 나가는 면의 방향은 총 6가지가 있다

(위로, 아래로, 앞면으로, 뒷면으로, 오른쪽 면으로, 왼쪽 면으로)

윗면과 아랫면의 면적 수는 무조건 주어진 좌표 직사각형의 넓이이니 (A.size() * A[0].size()) * 2는 무조건 잡고 시작한다

그리고 남은 4개의 방향은 각각의 방향에서 계산이 들어온다고 했을 때 마주하는 첫 면의 높이 + 첫 면을 시작으로 그 다음 면과 높이를 뺏을 때 음수값 (자세히 얘기하면 a[idx] - a[idx+1]이 음수인 경우 다음 블록이 음수만큼 높은 것임을 이용)

임을 이용하여 규칙을 구하고 계산하면 시간복잡도 O(n^2)에 문제를 해결할 수 있다.