[Leetcode] 3531. Count Covered Buildings

n 개의 빌딩 좌표를 주어진다. 이 빌딩들 중 상하좌우에 전부 다른 빌딩이 있는 빌딩의 숫자를 구하는 문제. 문제에서는 2차원 좌표를 위한 값을 주면서 배열을 만들어보라는 식으로 이야기하지만 n 이 최대값은 10^5 이기 때문에 배열이 되는 순간(O(N^2)이 되는 순간) 터질 수 밖에 없다.

모든 빌딩의 위치를 알아내서 각 행과 열의 최대최소값을 구해 O(2N) -> O(N)으로 끝내면 된다.

function countCoveredBuildings(n: number, buildings: number[][]): number {
    const rMap = new Map();
    const cMap = new Map();

    for (const building of buildings) {
        const [r, c] = building

        if (!Array.isArray(rMap.get(r))) {
            rMap.set(r, [c, c])
        } else {
            const [minC, maxC] = rMap.get(r)
            if (c < minC) {
                rMap.set(r, [c, maxC])
            }

            if (c > maxC) {
                rMap.set(r, [minC, c])
            }
        }

        if (!Array.isArray(cMap.get(c))) {
            cMap.set(c, [r, r])
        } else {
            const [minR, maxR] = cMap.get(c)

            if (r < minR) {
                cMap.set(c, [r, maxR])
            }

            if (r > maxR) {
                cMap.set(c, [minR, r])
            }
        }
    }

    let answer = 0;

    for (const building of buildings) {
        const [r, c] = building;
        const [minC, maxC] = rMap.get(r)
        const [minR, maxR] = cMap.get(c)

        if (minR < r && r < maxR && minC < c && c < maxC) {
            answer += 1;
        }
    }

    return answer;
};