파이썬(Python)으로 x축·y축에 평행한 정사각형을 만드는 네 점 찾기

n개의 좌표 점이 주어졌을 때, 그중 네 점을 골라 변이 x축과 y축에 평행한 정사각형을 만들어야 합니다. 조건을 만족하는 정사각형을 만들 수 없다면 "만들 수 없음"을 반환하고, 정사각형을 여러 개 만들 수 있다면 그중 면적이 가장 큰 것을 선택해야 합니다.

예를 들어 입력이 n = 6, points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]라면 출력은 다음과 같습니다.

변의 길이(side): 3
꼭짓점(points): (2, 2), (5, 2), (2, 5), (5, 5)

접근 방법

이 문제는 해시 맵(파이썬의 딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

모든 점을 딕셔너리에 미리 저장해 두면, 특정 좌표가 점 목록에 존재하는지 상수 시간(O(1))에 확인할 수 있습니다.
두 점 (i, j)를 정사각형의 대각선 꼭짓점 후보로 삼습니다. 두 점의 x좌표 차이와 y좌표 차이의 절댓값이 서로 같다면(|dx| = |dy|), 나머지 두 꼭짓점은 반드시 (xi, yj)와 (xj, yi)가 됩니다.
딕셔너리를 조회해 나머지 두 꼭짓점이 실제로 존재하는지 확인하고, 존재한다면 하나의 정사각형이 완성됩니다.
완성된 정사각형의 변 길이가 지금까지 찾은 최댓값보다 크면 결과를 갱신합니다.

알고리즘 단계

모든 점의 좌표를 키로 하는 딕셔너리 my_map을 생성하고, 각 좌표의 등장 횟수를 값으로 저장합니다.
side, x, y를 각각 -1로 초기화합니다. side는 최대 변의 길이, (x, y)는 결과 정사각형의 기준 꼭짓점을 의미합니다.
모든 점 쌍 (i, j)에 대해 두 점을 임시로 딕셔너리에서 제외한 뒤, |xi − xj| = |yi − yj|를 만족하는지 검사합니다.
조건을 만족하면 (xi, yj)와 (xj, yi)가 딕셔너리에 남아 있는지 확인합니다.
네 꼭짓점이 모두 존재하는 유효한 정사각형이라면, 변 길이가 기존 최댓값보다 클 때 side, x, y를 갱신합니다.
탐색이 끝난 뒤 side가 여전히 -1이라면 "No such square"를 출력하고, 그렇지 않으면 변의 길이와 네 꼭짓점을 출력합니다.

구현 예제

다음 파이썬 코드로 위 알고리즘을 구현할 수 있습니다.

def get_square_points(points, n):
    # 모든 점을 딕셔너리에 저장 (특정 좌표의 존재 여부를 빠르게 확인)
    my_map = dict()
    for i in range(n):
        my_map[(points[i][0], points[i][1])] = my_map.get((points[i][0], points[i][1]), 0) + 1

    side = -1   # 찾은 정사각형 중 최대 변의 길이
    x = -1      # 결과 정사각형의 기준 꼭짓점 x좌표
    y = -1      # 결과 정사각형의 기준 꼭짓점 y좌표

    for i in range(n):
        my_map[(points[i][0], points[i][1])] -= 1
        for j in range(n):
            my_map[(points[j][0], points[j][1])] -= 1
            # 두 점이 대각선 꼭짓점이 될 수 있는지 확인 (|dx| == |dy|)
            if (i != j and abs(points[i][0] - points[j][0]) == abs(points[i][1] - points[j][1])):
                # 나머지 두 꼭짓점이 점 목록에 존재하는지 확인
                if (my_map.get((points[i][0], points[j][1]), 0) > 0 and my_map.get((points[j][0], points[i][1]), 0) > 0):
                    # 더 큰 정사각형을 찾았다면 결과 갱신
                    if side < abs(points[i][0] - points[j][0]):
                        x = points[i][0]
                        y = points[i][1]
                        side = abs(points[i][0] - points[j][0])
            my_map[(points[j][0], points[j][1])] += 1
        my_map[(points[i][0], points[i][1])] += 1

    if side != -1:
        print("Side:", side)
        print("Points:", (x, y), (x + side, y), (x, y + side), (x + side, y + side))
    else:
        print("No such square")


n = 6
points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]
get_square_points(points, n)

입력

6, [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]

출력

Side: 3
Points: (2, 2) (5, 2) (2, 5) (5, 5)

복잡도 분석

시간 복잡도: 모든 점 쌍을 비교해야 하므로 O(n²)입니다.
공간 복잡도: 점의 존재 여부를 저장하는 딕셔너리 때문에 O(n)입니다.