LeetCode

LeetCode 2013 Detect Squares 풀이: 좌표 빈도 해시

2026년 9월 16일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 2013. Detect Squares
출처: LeetCode
자체 판단 난이도: Level 3

점의 추가와 쿼리 시점의 정사각형 개수 계산을 함께 지원하는 자료구조를 설계해야 한다. 축에 평행한 정사각형의 좌표 관계를 찾아야 하고, 같은 점이 여러 번 추가될 때 경우의 수에 반영해야 하므로 Level 3으로 판단했다.

1. 문제 요약

2차원 평면에 점이 순서대로 추가된다. 같은 좌표의 점을 여러 번 추가할 수 있으며, 중복 점은 서로 다른 점으로 취급한다.

count([x, y])가 호출되면 쿼리 점 [x, y]와 데이터 구조에서 고른 세 점이 양의 넓이를 가지는 축에 평행한 정사각형을 이루는 경우의 수를 반환해야 한다.

축에 평행한 정사각형의 변은 x축 또는 y축과 평행하다.
정사각형의 변 길이는 양수여야 한다.
좌표는 0 이상 1000 이하다.
add와 count 호출은 전체 최대 3000회다.

예를 들어 [3, 10], [11, 2], [3, 2]가 저장되어 있을 때 쿼리 [11, 10]은 네 점이 한 변의 길이 8인 정사각형을 이루므로 1을 반환한다. [11, 2]를 한 번 더 추가하면 같은 좌표의 선택지가 2배가 되어 결과가 2가 된다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그래프 구조와 방문 기록

점의 좌표를 키로 하고, 같은 점이 추가된 횟수를 값으로 저장한다.

counts[x][y] = 좌표 (x, y)가 추가된 횟수

쿼리 점을 P = (x1, y1), 후보 점을 Q = (x2, y2)라고 하자. 두 점을 축에 평행한 정사각형의 대각선으로 사용하려면 다음 조건이 필요하다.

x1 != x2
abs(x2 - x1) == abs(y2 - y1)

이 조건을 만족하면 나머지 두 꼭짓점은 다음과 같이 유일하게 정해진다.

(x1, y2), (x2, y1)

따라서 세 점의 등장 횟수를 곱하면 해당 후보 대각선이 만드는 선택 경우의 수가 된다.

counts[x2][y2] * counts[x1][y2] * counts[x2][y1]

대각선 후보와 빈도 곱으로 정사각형 세기

축에 평행한 정사각형에서 서로 마주 보는 두 꼭짓점은 x좌표 차이와 y좌표 차이의 절댓값이 같다. 쿼리 점과 이 조건을 만족하는 저장 점을 하나 고르면 나머지 두 점의 위치가 정해지므로, 모든 점 쌍을 조합할 필요 없이 후보 점을 순회하며 세 좌표를 조회하면 된다.

중복 점은 단순히 집합에 넣으면 안 된다. 네 꼭짓점 중 각 좌표가 추가된 횟수를 곱해야 서로 다른 점 선택을 모두 세기 때문이다.

상태 전이와 경계 처리

add(point)는 해당 좌표의 빈도를 1 증가시킨다. count(point)는 저장된 각 x좌표와 그 안의 y좌표를 확인하면서 다음 순서로 처리한다.

쿼리 점과 같은 x좌표인 후보는 건너뛴다. 변의 길이가 0인 정사각형이 되기 때문이다.
x좌표 차이와 y좌표 차이의 절댓값이 다르면 건너뛴다.
나머지 두 꼭짓점의 빈도를 조회한다.
세 빈도의 곱을 결과에 더한다.

쿼리 점과 같은 x좌표의 저장 점이 없거나 필요한 꼭짓점이 없으면 빈도 조회 결과가 0이므로 자동으로 해당 후보가 결과에 기여하지 않는다.

오답 접근과 반례

중복 점을 set에 저장하면 같은 좌표가 여러 번 추가된 사실을 잃는다.

add([0, 0]), add([0, 1]), add([1, 0]), add([1, 1]), add([1, 1])
count([0, 0])

쿼리 점 [0, 0]과 나머지 세 좌표로 정사각형을 만들 수 있고, [1, 1]이 두 번 추가되었으므로 정답은 2다. 좌표 존재 여부만 저장하면 1로 잘못 계산한다.

후보 점과 쿼리 점의 x·y 차이를 확인하지 않고 인접한 점처럼 처리하면 축에 평행하지 않은 도형이나 직사각형을 정사각형으로 셀 수 있다. 두 차이의 절댓값이 같은지 반드시 확인해야 한다.

시간·공간 복잡도

add는 해시 맵 갱신 한 번이므로 평균 O(1)이다. count는 저장된 서로 다른 점을 순회하므로 최악의 시간 복잡도는 O(P)이며, P는 저장된 서로 다른 좌표 수다. 점의 빈도를 저장하는 공간 복잡도는 O(P)다.

3. 문제 해결 코드 (Python)

from collections import Counter, defaultdict


class DetectSquares:
    def __init__(self):
        self.counts = defaultdict(Counter)

    def add(self, point: list[int]) -> None:
        x, y = point
        self.counts[x][y] += 1

    def count(self, point: list[int]) -> int:
        x1, y1 = point
        answer = 0
        same_x = self.counts.get(x1, {})

        for x2, y_counts in self.counts.items():
            if x1 == x2:
                continue

            side = x2 - x1
            for y2, frequency in y_counts.items():
                if abs(y2 - y1) != abs(side):
                    continue

                answer += frequency * same_x.get(y2, 0) * y_counts.get(y1, 0)

        return answer

same_x는 쿼리 점과 같은 x좌표에 저장된 y좌표 빈도다. 쿼리 x좌표가 아직 한 번도 등장하지 않은 경우에도 빈 딕셔너리처럼 조회해 안전하게 0을 반환한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 정사각형 탐지와 중복 점의 빈도 처리를 확인할 수 있다.

squares = DetectSquares()
squares.add([3, 10])
squares.add([11, 2])
squares.add([3, 2])
assert squares.count([11, 10]) == 1
squares.add([11, 2])
assert squares.count([11, 10]) == 2

4. 공식 예제와 추가 검증

공식 예제와 중복 점, 빈 꼭짓점, 쿼리 점의 x좌표가 없는 경우를 Python 코드로 실행했다.

공식 예제

입력:
add([3, 10]), add([11, 2]), add([3, 2])
count([11, 10])

기대 출력: 1
확인 결과: 통과
검증 목적: 쿼리 점과 대각선을 이루는 후보를 찾고 나머지 꼭짓점을 조회하는지 확인

추가 입력: add([11, 2]), count([11, 10])
기대 출력: 2
확인 결과: 통과
검증 목적: 중복 점의 빈도가 정사각형 선택 경우의 수에 곱해지는지 확인

추가 검증 1: 중복 꼭짓점

입력: add([0, 0]), add([0, 1]), add([1, 0]), add([1, 1]), add([1, 1])
count([0, 0])
기대 출력: 2
확인 결과: 통과
검증 목적: 동일 좌표의 중복 추가를 서로 다른 선택으로 세는지 확인

추가 검증 2: 쿼리 점이 없는 정사각형

입력: add([1, 1]), add([1, 3]), add([3, 1]), count([3, 3])
기대 출력: 1
확인 결과: 통과
검증 목적: 쿼리 점은 데이터 구조에 미리 추가되지 않아도 정사각형을 완성할 수 있는지 확인

추가 검증 3: 후보가 없는 쿼리

입력: add([1, 1]), add([1, 3]), add([3, 1]), count([100, 100])
기대 출력: 0
확인 결과: 통과
검증 목적: 필요한 대각선과 꼭짓점이 없을 때 0을 반환하는지 확인

5. 다른 풀이 방식 검색 및 비교

Detect Squares 공식 문제는 점 추가, 중복 점 처리, 축에 평행한 양의 넓이 정사각형 개수 조회를 정의한다.
NeetCode의 Detect Squares 설명은 점 좌표별 빈도 해시와 후보 대각선을 이용해 나머지 꼭짓점을 조회하는 접근을 설명한다.

좌표를 2차원 배열에 저장하는 방식도 좌표 범위가 작다는 점을 이용해 구현할 수 있다. 이 글에서는 좌표 빈도만 저장하는 중첩 해시를 사용해 필요한 데이터만 관리했다. 후보 점마다 대각선 조건을 확인하는 방식은 count 한 번에 O(P) 시간이 필요하지만, 전체 호출 수가 3000회 이하라는 제한 안에서 충분하다. 가장 중요한 차이는 중복 점을 빈도로 저장해 결과에 곱하는 것이다.

마무리

Detect Squares는 좌표 기하 관계를 해시 조회로 바꾸는 자료구조 설계 문제다. 쿼리 점과 대각선을 이루는 후보를 찾으면 나머지 두 꼭짓점이 결정되고, 네 좌표의 빈도를 곱해 중복 점까지 정확히 셀 수 있다. add는 평균 O(1), count는 저장된 좌표 수에 비례하는 시간으로 처리할 수 있다.