[백준 9015번] 정사각형 (Python3)

import sys
input = sys.stdin.readline

for _ in range(int(input())):
  N = int(input())
  co = [tuple(map(int,input().split())) for i in range(N)]
  check = {*co}
  
  result = 0
  for i in range(N):
    x1,y1 = co[i]
    for j in range(i+1,N):
      x2,y2 = co[j]
      dx,dy = x1-x2,y1-y2
      if (x1+dy,y1-dx) in check and (x2+dy,y2-dx) in check or (x1-dy,y1+dx) in check and (x2-dy,y2+dx) in check:
        result = max(result,dx**2+dy**2)
  print(result)

파이썬 set을 이용하여 해결하였다.

입력값에 비해 시간제한이 넉넉하기 때문에 O(N^2)으로 해결할 수 있다.

 

풀이를 설명하면,

1. 모든 좌표를 튜플로 저장하고, 좌표들에 대한 set을 만든다.

2. 2중 for문을 돌면서 두 좌표를 잡고 두 좌표의 x좌표의 차이와 y좌표의 차이를 dx,dy로 둔다.

3. 두 좌표의 정사각형을 이룰 수 있는 좌표에 좌표가 존재하는지를 검사한다.

4. 좌표가 존재하면 dx^2+dy^2로 최댓값을 갱신한다.

 

1에서 set을 만드는 이유는 set의 in 함수의 시간복잡도가 O(1)이기 때문이다.

4번은 피타고라스의 정리에 의해서 성립한다.

 

 

오늘의 교훈) set은 유용하다.