[LeetCode] 3548 Equal Sum Grid Partition II (C/C++)

문제

https://leetcode.com/problems/equal-sum-grid-partition-ii

풀이

최근 CodeSignal 코딩 테스트를 대비하면서 LeetCode에서 매일 문제를 풀고 있다.

TMI이지만, 예전에 Moloco에 referral을 받을 기회가 있어서 CodeSignal로 코딩 테스트를 준비한 적이 있었다. 당시에는 회사 출근하면서 준비하느라, 준비를 잘못해 아쉬웠던 기억이 있다.

영어를 그렇게 못하는 편은 아니라고 생각해서 방심했는데, 이번 문제를 풀면서 그때의 기억과 기분이 꽤 생생하게 떠올랐다.

문제에 'either'라는 표현이 있었는데, 이걸 대충 읽고 'each'로 잘못 이해했다.

원래는 “양쪽 중 하나에서 최대 하나 제거 가능”인데, “양쪽 각각에서 하나씩 제거 가능”으로 이해해서 풀이를 아예 다른 방향으로 진행했다.

그래도 이번에는 다행이었다.

더 어려운 방향으로 구현하고 있었던 거라, 되돌리는 게 어렵지 않았고
LeetCode 특성상 테스트케이스가 충분히 공개되어 있어서 빠르게 틀린 걸 확인할 수 있었다

그래서 다시 구현하는 데 큰 문제는 없었다.

하지만 CodeSignal에서 다시 예전 Moloco 지원 때와 오늘처럼 문제를 잘못 이해해서 풀이 방향을 잘못 잡는 경우가 생긴다면, 쉽지 않겠다는 생각이 들었다.

제발,, 잘 읽자,,

정답 코드

C++17

static constexpr int MAX_VALUE = 100000;

class Section {
public:
    long long sum;
    std::vector<int> frequency;

    Section(): sum(0), frequency(MAX_VALUE + 1, 0) {}
    Section(const std::vector<std::vector<int>> &grid): Section() {
        for (const auto &row: grid) {
            this->insert(row);
        }
    }

    int insert(const std::vector<int> &row) {
        for (const auto value: row) {
            sum += value;
            frequency[value] += 1;
        }

        return 0;
    }

    int erase(const std::vector<int> &row) {
        for (const auto value: row) {
            sum -= value;
            frequency[value] -= 1;
        }

        return 0;
    }
};

class Solution {
private:
    std::vector<std::vector<int>> transpose(const std::vector<std::vector<int>> &source) {
        const size_t N = source.size();
        const size_t M = source[0].size();
        std::vector<std::vector<int>> ret(M, std::vector<int>(N));

        for (size_t i = 0; i < M; i++) {
            for (size_t j = 0; j < N; j++) {
                ret[i][j] = source[j][i];
            }
        }

        return ret;
    }

    bool discriminate(const std::vector<std::vector<int>> &grid) {
        const size_t N = grid.size();
        const size_t M = grid[0].size();
        Section top, bottom(grid);
    
        for (size_t i = 0; i < N - 1; i++) {
            top.insert(grid[i]); bottom.erase(grid[i]);
            
            const long long diff = top.sum - bottom.sum;
            const bool sumIsEqual = diff == 0;
            const bool canRemoveFromTop = 
                (0 < diff && diff <= MAX_VALUE) && 
                (top.frequency[diff] != 0) &&
                (i != 0 || diff == grid[0][0] || diff == grid[0][M - 1]) &&
                (M != 1 || diff == grid[0][0] || diff == grid[i][0]);
            const bool canRemoveFromBottom =
                (-MAX_VALUE <= diff && diff < 0) &&
                (bottom.frequency[-diff] != 0) &&
                (i != N - 2 || -diff == grid[N - 1][0] || -diff == grid[N - 1][M - 1]) &&
                (M != 1 || -diff == grid[i + 1][0] || -diff == grid[N - 1][0]);

            if (sumIsEqual || canRemoveFromTop || canRemoveFromBottom) {
                return true;
            }
        }

        return false;
    }

public:
    bool canPartitionGrid(const std::vector<std::vector<int>> &grid) {
        return discriminate(grid) || discriminate(transpose(grid));
    }
};

[LeetCode] 3548 Equal Sum Grid Partition II (C/C++)

문제

풀이

정답 코드

Share this post