[백준 2121] 넷이 놀기

문제

네 사람이서 2차원 평면상의 N개의 점을 이용해서 할 수 있는 놀이가 있다. 바로 각 사람이 1개씩의 점을 적절히 선택해서 변이 x축 혹은 y축에 평행한 직사각형을 만드는 일이다. 물론 그냥 만들면 재미가 없기 때문에 가로의 길이가 A 세로의 길이가 B인 직사각형을 몇 가지나 만들 수 있는지 알아보기로 했다.

예를 들어 점이 A(0, 0), B(2, 0), C(0, 3), D(2, 3), E(4, 0), F(4, 3)의 6개가 있고, 만들고 싶은 직사각형이 가로가 2, 세로가 3인 직사각형이라면 (A, B, C, D), (B, D, E, F)의 두 가지 경우가 가능하다. 모든 경우의 수를 구해보자.

입력

첫 줄에 점들의 개수 N(5 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에 만들고 싶은 직사각형의 가로 길이 A(1 ≤ A ≤ 1,000)와 세로 길이 B(1 ≤ B ≤ 1,000)가 주어진다. 다음 N줄에 걸쳐서 점들의 좌표가 정수로 주어진다. 이 값의 범위는 -1,000,000,000이상 1,000,000,000이하이다. N개 점들의 좌표는 각각 다르다.

출력

첫 줄에 가능한 모든 경우의 수를 출력한다. 경우의 수는 231-1보다 작거나 같다.

---

풀이

문제를 이해하고 가장 먼저 생각한 방법은 완전탐색이었다

모든 점을 기준으로 가로 A / 세로 B에 해당하는 직사각형 꼭짓점이 존재하는지 체크하기

 

점은 최대 500,000개까지 주어지며 한 점을 검사할 때에는 원하는 거리에 있는 세 개의 점이 존재하는지 확인해야한다

각 점들의 존재유무를 완전탐색으로 확인할 경우 O(N^2)가 걸려 시간 초과가 날 것이 뻔하니 선 정렬 후 이분탐색을 하려했으나

 

(x,y)자체를 키값으로 사용하여 해싱하면 각 점 탐색에 O(1)이 걸리므로 해시를 사용하면 O(N)으로 풀 수 있다

(x,y) (x+A,y) (x,y+B) (x+A,y+B) 를 모든 점을 기준으로 탐색하며 카운팅하면 끝

# 넷이 놀기
import sys
input = sys.stdin.readline

N = int(input())
w,h = map(int,input().split())
dots = set()
res = 0

for _ in range(N):
    x,y = map(int,input().split())
    dots.add((x,y))

for x,y in dots:
    if (x,y) in dots and (x+w,y) in dots and (x,y+h) in dots and (x+w,y+h) in dots:
        res += 1

print(res)

 

 

x in list > O(n)

x in dict > O(1)

x in set > O(1)

 

set과 dict에서 in의 동작은 해시로 동일하게 O(1)이지만

dict에서 in을 사용하면 value가 아닌 key들을 기준으로 탐색하고

set은 key로만 이루어지기에 위와 같이 value가 불필요한 경우는 set을 사용하는 것이 더 깔끔해보인다