3531. 덮인 건물 개수 세기

Source: Dev.to

Problem Description

양의 정수 n이 주어집니다. 이는 n × n 크기의 도시를 의미합니다.
또한 2차원 배열 buildings가 주어지며, buildings[i] = [x, y]는 좌표 [x, y]에 위치한 고유한 건물을 나타냅니다.

건물은 네 방향(왼쪽, 오른쪽, 위, 아래) 모두에 최소 하나의 건물이 있을 때 덮여 있다고 합니다.
덮여 있는 건물의 개수를 반환하세요.

Examples

Example 1

Input: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]
Output: 1

Explanation:
위쪽에 [1,2], 아래쪽에 [3,2], 왼쪽에 [2,1], 오른쪽에 [2,3]이 각각 존재하므로 [2,2]만이 덮여 있습니다.

Example 2

Input: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
Output: 0

Explanation:
네 방향 모두에 이웃이 있는 건물이 없습니다.

Example 3

Input: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
Output: 1

Explanation:
위쪽에 [1,3], 아래쪽에 [5,3], 왼쪽에 [3,2], 오른쪽에 [3,5]가 있어 [3,3]만이 덮여 있습니다.

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ buildings.length ≤ 10⁵
• buildings[i] = [x, y]
• 1 ≤ x, y ≤ n
• 모든 건물 좌표는 서로 다릅니다.

Hint

같은 x 혹은 y 값을 가진 건물들을 그룹화하고, 각 그룹을 정렬하세요.
정렬된 리스트에서 첫 번째와 마지막 위치에 있지 않은 건물들은 해당 방향에서 이웃이 존재합니다.

Solution Overview

각 건물이 네 방향 모두에 최소 하나의 이웃이 있는지를 판단해야 합니다.
건물 수를 m이라 할 때 O(m²) 검사는 너무 느립니다.
대신 다음과 같이 진행합니다.

1. 건물을 열(x)과 행(y) 별로 그룹화합니다.
2. 각 그룹을 정렬합니다.
3. 정렬된 열·행 내에서 건물의 위치를 확인해 위/아래와 왼쪽/오른쪽 이웃 존재 여부를 추론합니다.
4. 네 방향 모두 이웃이 있는 건물을 카운트합니다.

Algorithm Details

Grouping by coordinates

• xMap[x] → 열 x에 있는 건물들의 y 값 리스트.
• yMap[y] → 행 y에 있는 건물들의 x 값 리스트.

Determining vertical coverage (above / below)

각 열 x에 대해 xMap을 순회합니다:

1. y 값들을 정렬합니다.
2. 해당 열의 건물 (x, y)마다
   • 가장 작은 y가 아니면 위에 건물이 존재합니다.
   • 가장 큰 y가 아니면 아래에 건물이 존재합니다.

Determining horizontal coverage (left / right)

각 행 y에 대해 yMap을 순회합니다:

1. x 값들을 정렬합니다.
2. 해당 행의 건물 (x, y)마다
   • 가장 작은 x가 아니면 왼쪽에 건물이 존재합니다.
   • 가장 큰 x가 아니면 오른쪽에 건물이 존재합니다.

Counting covered buildings

각 건물에 대해 네 개의 불리언 플래그(above, below, left, right)를 저장합니다.
두 차원을 모두 처리한 뒤, 네 플래그가 모두 true인 건물을 카운트합니다.

Complexity Analysis

• Time: O(m log m), 여기서 m = buildings.length.

  • 그룹화: O(m)
  • 각 그룹 정렬 (전체 합): O(m log m)
  • 플래그 설정을 위한 스캔: O(m)

• Space: O(m) – 그룹 맵과 상태 저장을 위한 추가 공간.

Reference Implementation (PHP)

// list of y, y => list of x
$xMap = [];
$yMap = [];

// Store each building's index for quick status updates
$indexMap = []; // "x,y" => idx
foreach ($buildings as $idx => $b) {
    [$x, $y] = $b;
    $xMap[$x][] = $y;
    $yMap[$y][] = $x;
    $indexMap["$x,$y"] = $idx;
}

// Status flags: each entry is ['above'=>false,'below'=>false,'left'=>false,'right'=>false]
$status = array_fill(0, $m, [
    'above' => false,
    'below' => false,
    'left'  => false,
    'right' => false,
]);

// Vertical check (above / below)
foreach ($xMap as $x => $ys) {
    sort($ys, SORT_NUMERIC);
    $cnt = count($ys);
    foreach ($ys as $pos => $y) {
        $idx = $indexMap["$x,$y"];
        if ($pos > 0) {
            $status[$idx]['above'] = true;   // there is a smaller y (above)
        }
        if ($pos < $cnt - 1) {
            $status[$idx]['below'] = true;   // there is a larger y (below)
        }
    }
}

// Horizontal check (left / right)
foreach ($yMap as $y => $xs) {
    sort($xs, SORT_NUMERIC);
    $cnt = count($xs);
    foreach ($xs as $pos => $x) {
        $idx = $indexMap["$x,$y"];
        if ($pos > 0) {
            $status[$idx]['left'] = true;    // smaller x exists
        }
        if ($pos < $cnt - 1) {
            $status[$idx]['right'] = true;   // larger x exists
        }
    }
}

// Count covered buildings
$covered = 0;
foreach ($status as $flags) {
    if ($flags['above'] && $flags['below'] && $flags['left'] && $flags['right']) {
        $covered++;
    }
}
return $covered;