1. 문제 소개

3531. Count Covered Buildings

2. 나의 풀이

처음에는 dict를 사용해 x축, y축마다 정리해 풀려고 했었다.
그러나 좌표별로 최대값과 최소값을 정리해두고 푸는 것이 낫다는 것을 확인하고 아래와 같이 풀었다.
전체 빌딩 수를 $m$이라고 할 때, 시간복잡도는 $O(m)$이다.

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        # 각 행/열별로 건물 좌표의 최솟값/최댓값을 기록할 배열 초기화
        x_max = [0] * (n+1)        # y를 인덱스로 사용, 해당 행(y)에서의 x 최댓값
        x_min = [n+1] * (n+1)      # y를 인덱스로 사용, 해당 행(y)에서의 x 최솟값
        y_max = [0] * (n+1)        # x를 인덱스로 사용, 해당 열(x)에서의 y 최댓값
        y_min = [n+1] * (n+1)      # x를 인덱스로 사용, 해당 열(x)에서의 y 최솟값

        # 1차 스캔: 모든 건물에 대해 행/열별 최소·최대 좌표를 갱신
        for x, y in buildings:
            x_max[y] = max(x_max[y], x)   # 행 y에서 x의 최댓값 갱신
            x_min[y] = min(x_min[y], x)   # 행 y에서 x의 최솟값 갱신
            y_max[x] = max(y_max[x], y)   # 열 x에서 y의 최댓값 갱신
            y_min[x] = min(y_min[x], y)   # 열 x에서 y의 최솟값 갱신

        ans = 0
        # 2차 스캔: 각 건물이 양쪽에 이웃을 가지는지(covered) 조건 확인
        for x, y in buildings:
            # 같은 행(y)에서 왼쪽/오른쪽에 다른 건물이 존재해야 하므로:
            #   x_min[y] < x < x_max[y]
            # 같은 열(x)에서 아래/위에 다른 건물이 존재해야 하므로:
            #   y_min[x] < y < y_max[x]
            if x_min[y] < x < x_max[y] and y_min[x] < y < y_max[x]:
                ans += 1   # 두 조건을 모두 만족하면 covered 건물로 카운트
        
        return ans         # 최종 covered 건물의 개수 반환

3. 다른 풀이

처음 생각한 풀이 방법도 존재했다.
이경우도 전체 빌딩 수를 $m$이라고 할 때, 시간복잡도는 $O(m\, log m)$이다.

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        rowMap = defaultdict(list)   # rowMap[x]  = 열(x) 위에 존재하는 y 좌표들의 정렬 리스트
        colMap = defaultdict(list)   # colMap[y]  = 행(y) 위에 존재하는 x 좌표들의 정렬 리스트

        # 각 건물을 행/열 단위로 정렬 리스트에 삽입 (bisect.insort 사용)
        # 삽입 시 자동으로 정렬 상태를 유지함
        for x, y in buildings:
            bisect.insort(rowMap[x], y)  # 열 x에 y 삽입
            bisect.insort(colMap[y], x)  # 행 y에 x 삽입

        ans = 0

        # 각 건물이 상하좌우로 둘러싸인 내부 건물인지 판정
        for x, y in buildings:
            row = colMap[y]   # 같은 행(y)에 있는 모든 x 좌표 리스트 (정렬된 상태)
            col = rowMap[x]   # 같은 열(x)에 있는 모든 y 좌표 리스트 (정렬된 상태)

            # 열(x) 기준에서 자기 y의 위치를 찾고 상/하 건물이 존재하는지 확인
            idx_col = bisect.bisect_left(col, y)
            top = col[idx_col + 1] if idx_col + 1 < len(col) else None      # 위쪽 건물(y보다 큰 y)
            down = col[idx_col - 1] if idx_col - 1 >= 0 else None           # 아래쪽 건물(y보다 작은 y)

            # 행(y) 기준에서 자기 x의 위치를 찾고 좌/우 건물이 존재하는지 확인
            idx_row = bisect.bisect_left(row, x)
            right = row[idx_row + 1] if idx_row + 1 < len(row) else None    # 오른쪽 건물(x보다 큰 x)
            left = row[idx_row - 1] if idx_row - 1 >= 0 else None           # 왼쪽 건물(x보다 작은 x)

            # 상/하/좌/우 모두 존재하면 내부 건물로 인정
            if top is not None and down is not None and left is not None and right is not None:
                ans += 1

        return ans

4. 마무리

그래도 문제가 쉬운 편이었다.