[백준/5419] 북서풍 (Python)

Problem : https://www.acmicpc.net/problem/5419

5419번: 북서풍

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 02:40:24

 

---

 

문제 설명

 

 

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.

작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 xi, yi가 주어진다. 두 섬의 좌표가 같은 경우는 없다. (-109 ≤ xi, yi ≤ 109)

 

출력

 

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

 

입력 예시

 

2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1

 

출력 예시

 

5
3

 

 

---

 

풀이

 

아래는 장대한 삽질을 최대한 요약해본 내용이다...

 

1. 아 이건 2차원 구간합이겠다..! 싶어서 2차원 세그먼트트리를 사용하기로 마음먹었다. 적당히 좌표 압축을 시켜 주면(dictionary로 rank 이용) 되겠고, 2차원 list를 새로 생성해서 mapping을 적용. 결과는 메모리 초과.

 

2. 좌표 압축에 사용되는 rank에 딕셔너리를 사용했으므로 해시값이 매우 커질 수 있겠다는 생각이 들었다. rank를 sort된 unique 리스트로 저장하고, binary search를 진행하는 식으로 풀이했다. binary search 중 lower bound 결과가 그 값의 rank가 되니까. 이 경우도 메모리 초과.

 

3. 세그먼트 트리의 공간복잡도를 생각할 때, 4*xlen*ylen이 되는 게 자명했다. 즉 2차원 펜윅 트리로 진행해보면 어떨까 싶었다. 공간복잡도는 xlen*ylen이 될 테니. 이 경우도 메모리 초과.

 

4. 뭘 놓치고 있지...? 라는 생각이 들 때쯤, 떠오른 것. 간단하게 동서남북 없이 (x, y) 이상의 모든 값들을 전부 업데이트하고 싶다고 하자.

우리가 좌표를 내림차순으로 정렬된 채로 차례대로 세그먼트 트리(혹은 펜윅 트리)에 업데이트한다면, (x, y) ~ (X, Y)의 넓이를 구하는 시점에서 x 이하, y 이하의 값은 절대 영향을 끼치지 못한다. x 이하의 기존 값들은 부분합을 구하면서 자연스럽게 제거되고, y 이하의 값은 아직 등장하지 않았기 때문이다. 즉 이렇게 좌표를 정렬하고 차례대로 방문하는 테크닉, 스위핑이 마지막 빠진 조각이었다. 스위핑을 수행하면 세그먼트 트리 혹은 펜윅 트리는 1차원으로 감소한다. y축은 같거나 작은 값, x좌표는 같거나 큰 값이 영향을 끼치므로 적당히 좌표만 추가로 가공하면 된다.

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = float('inf')

def coord_compress(coord, N) :
  length = [0]*2
  prev = [-MAX]*2
  for i in range(2) :
    coord.sort(key = lambda x : (x[i], x[1-i]))
    for j in range(N) :
      if prev[i] < coord[j][i] :
        prev[i] = coord[j][i]
        length[i] += 1
      coord[j][i] = length[i]
  return coord, length[0]+1, length[1]+1

def update(i, xlen) :
  while i <= xlen :
    tree[i] += 1
    i += -i & i
def search(i) :
  result = 0
  while i :
    result += tree[i]
    i -= -i & i
  return result

def solve() :
  global tree
  N = int(input())
  coord = [list(map(int, input().split())) for _ in range(N)]
  coord, xlen, ylen = coord_compress(coord, N)
  coord.sort(key = lambda x : (x[1], -x[0]))
  tree = [0]*(xlen + 1)
  result = 0
  for x, _ in coord :
    result += search(xlen-x)
    update(xlen-x, xlen)
  print(result)

for _ in range(int(input())) :
  solve()

풀이 완료!