사용자 도구

사이트 도구


ps:problems:boj:5419

북서풍

ps
링크acmicpc.net/…
출처BOJ
문제 번호5419
문제명북서풍
레벨플래티넘 4
분류

Order Statistic Tree

시간복잡도O(T * nlogn)
인풋사이즈n <= 75000, T <= ???
사용한 언어Python
제출기록59548KB / 4240ms
최고기록4240ms
해결날짜2021/04/09
태그

39단계

풀이

  • 기본적인 Inversion Counting 문제.
  • 좌표의 범위가 크므로 좌표 압축이 필요하다
  • 시간 복잡도는 O(nlogn)..인데 테스트 케이스가 여러개이다.
  • 테스트 케이스의 갯수가 주어지지 않는데 수가 적지는 않은것 같다. n의 범위가 75000이하밖에 안되는데도 Python으로는 시간이 상당히 빡빡하다. 처음에는 Python으로는 포기하고 PyPy로 제출했었는데. 그 뒤에 python3으로 통과한 사람이 생긴 것을 보고서 나도 조금 더 최적화를 하다보니 아슬아슬하게 시간 내에 들어왔다. 좌표 압축하는 루틴을 작성할때 보통은 가독성을 위해서 set을 이용해서 중복값을 제거하거나, itertools.groupby를 써서 중복값을 처리하거나 하는 방식으로 해왔는데, 이번에는 그냥 수작업으로 풀어서 처리했다.

코드

"""Solution code for "BOJ 5419. 북서풍".

- Problem link: https://www.acmicpc.net/problem/5419
- Solution link: http://www.teferi.net/ps/problems/boj/5419
"""

import operator
import sys
from teflib import fenwicktree


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        points = [[int(x) for x in sys.stdin.readline().split()] 
                  for _ in range(n)]

        points.sort(key=operator.itemgetter(1))
        compressed_y = 0
        prev = points[0][1]
        for point in points:
            if point[1] != prev:
                prev = point[1] 
                compressed_y += 1
            point[1] = compressed_y
        answer = 0
        fenwick = fenwicktree.FenwickTree(n)
        for _, y in sorted(points, key=lambda p: -p[0]):
            answer += fenwick.query(0, y + 1)
            fenwick.update(y, 1)

        print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U᠎ K X K O
 
ps/problems/boj/5419.txt · 마지막으로 수정됨: 2021/05/05 16:35 저자 teferi