좌표평면 위의 직사각형 면적 구하기 - python

문제

좌표평면위에 여러 개의 점이 찍혀있다. [x, y]형식으로 주어진다. 이 점들을 이어서 직사각형을 만들 수 있는 모든 경우에 대해 가장 넓은 직사각형의 넓이를 구하여라. 만약 직사각형을 만들 수 없다면 -1을 리턴하라. 단, 직사각형이 x, y축에 평행한 경우만 고려한다.

 

입출력 예시 1)
input = [[1,1], [4,1], [4,6], [1,6] ,[4,3], [2,3], [2,1], [2,0] ,[4,10], [1,10], [6, 10]]
output = 27

입출력 예시 2)
input = [[4,1], [1,1], [4,6], [1,6] ,[4,3], [2,3], [2,1]]
Output = 15

입출력 예시 3)
input = [[2,1], [2,0] ,[4,10], [1,10]]
Output = -1

 

-

보기엔 정말 간단한 문제 같다.

그냥 점 4개를 골라서 직사각형인지 체크하고 면적을 구하면 되는거 아닌가?

그런데 직사각형인지 체크하는 로직이 생각보다 깔끔하지 못했고....

소스가 더러워져 결국 시간내에 문제를 풀지 못했다...하하

 

며칠동안 뇌에서 떠나지 않아 결국 다시 풀어보았다.

 

풀이 1

파이썬 라이브러리 중 콤비네이션을 리턴해주는 함수가 있다. 이를 이용해서 모든 경우의 4개의 점을 찾고, 그 점이 사각형인지 판별한 다음 면적을 구하는 방식이다.

콤비네이션을 뽑아내는 것 부터가 비효율적일수 있지만, 가장 먼저 떠오르는 방식이다.

 

from itertools import combinations

def getSquareArea(points) :
    visited = [points[0]]
    points = points[1:]
    curr = visited[0][1]
    axis_cur = 1
    while len(visited) < 4:
        for idx, p in enumerate(points):
            if p[axis_cur] == curr:
                visited.append(p)
                points.pop(idx)
                axis_cur =  0 if axis_cur == 1 else 1
                curr = p[axis_cur]
                break
        else:
            return -1
    if curr == visited[0][0]:
        return abs(visited[0][0] - visited[1][0]) * abs(visited[1][1] - visited[2][1])
    return -1
    
    
    
# input = [[4,1], [1,1], [4,6], [1,6] ,[4,3], [2,3], [2,1]]
input = [[2,1], [2,0] ,[4,10], [1,10]]
new = combinations(input, 4)
result = -1
for n in new:
    result = max(getSquareArea(list(n)), result)
print(result)

네모를 판별하는 부분이 조금 더럽다고 느껴졌다.

내가 생각한 방식은 점 4개를 다 훑으면서 첫 번째 좌표의 y좌표와 같은 y좌표값을 갖는 점이 있는지 확인한다.

만약 있다면 그 점의 x좌표와 같은 x좌표 값을 갖는 점이 있는지 확인한다.

이런식으로 쭉 돌아서 4개가 모두 연쇄적으로 이어지면 맨 마지막 점의 x 좌표와 맨 첫 점의 x좌표를 확인한다.

그 두 값이 같다면 네모로 이어지는 것이다.

이럴 때 두 변의 길이를 구해서 곱해준다. 

 

이 계산을 모든 조합에 대해 하게 된다.

 

풀이 2.

from collections import defaultdict
input = [[1,1], [4,1], [4,6], [1,6] ,[4,3], [2,3], [2,1], [2,0] ,[4,10], [1,10], [6, 10]]
# input = [ [2,0] ,[4,10], [1,10], [6, 10]]
output = -1
xy = defaultdict(list) #key: x좌표, value: y좌표 리스트
for x, y in input:
    xy[x].append(y)
xlist = list(xy.keys()) #x좌표 리스트

for x1_idx, x1 in enumerate(xlist):
    for x2_idx, x2 in enumerate(xlist[:x1_idx]):
        dx = abs(x2 - x1)
        dy = 0
        
        ylist = [y for y in xy[x1] if y in xy[x2]] #x1, x2에 공통적으로있는 y좌표리스트 
        for y1 in ylist:
            for y2 in ylist[1:]:
                dy = max(dy, abs(y2 - y1))
                output = max(output, dy*dx)
print(output)

일단 자료구조를 먼저 만들어 놓는다.

x좌표값을 키로 갖고, 그 x값을 갖는 모든 점들의 y좌표 값들을 list로 value가 되는 딕셔너리를 만든다.

그 다음 x좌표 리스트 중에서 중복없이 2개씩 x좌표값(x1, x2)을 가져온 다음 해당하는 y좌표 리스트 2개를 가져온다.

y좌표리스트 두개 중 공통적으로 들어있는 좌표가 2개이상 있다면, 네모가 만들어진다.

그 중에서 가장 넓은 너비를 구한다.

 

이렇게 하다보니 4중 포문이 되어버렸다.

하지만 콤비네이션을 하는 것보단 빠른 것 같긴 하다.

 

이로써 직사각형문제는 훌훌 털어버림.

-끝-