사용자 도구

사이트 도구


ps:problems:boj:7568

덩치

ps
링크acmicpc.net/…
출처BOJ
문제 번호7568
문제명덩치
레벨실버 5
분류

OrderStatisticTree

시간복잡도O(nlogn)
인풋사이즈n<=50
사용한 언어Python
제출기록33996KB / 156ms
최고기록52ms
해결날짜2021/10/05

풀이

  • 2-tuple의 리스트가 주어졌을때, 각각에 대해서 도미넌트한 튜플의 갯수를 세는 문제. 북서풍와 거의 유사한 문제이고, 관련 풀이는 Inversion Counting을 참고하면 된다.
  • 하지만 북서풍이 플래티넘 난이도인것에 비해 이 문제는 실버인 이유는, n이 최대 50밖에 안돼서, 그냥 O(n^2) 알고리즘으로 돌려도 충분하기 때문. 여기에서는 정해인 O(nlogn) 풀이만 올렸지만, O(n^2) 알골리즘이 코드가 훨씬 간단한것은 당연하고, 실행시간에서조차도 펜윅트리로 구현하는 O(nlogn) 알고리즘 보다도 더 빨리 실행된다.

코드

"""Solution code for "BOJ 7568. 덩치".

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

Tags: [OrderStatisticTree]
"""

from teflib import fenwicktree


def main():
    N = int(input())
    heights, weights = [], []
    for _ in range(N):
        x, y = [int(x) for x in input().split()]
        weights.append(x)
        heights.append(y)

    ost = fenwicktree.OrderStatisticTree(max(heights) + 1)
    ranks = [None] * N
    order_by_weight = sorted(range(N), key=lambda i: (-weights[i], heights[i]))
    for i in order_by_weight:
        h = heights[i]
        ranks[i] = ost.size() - ost.count_less_than(h) - ost.count(h) + 1
        ost.add(h)

    print(*ranks)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P᠎ D G J R
 
ps/problems/boj/7568.txt · 마지막으로 수정됨: 2021/10/05 16:51 저자 teferi