어떤게임에서는 점수에 따라 랭크 승격시스템을 사용하는데
그 랭크 승격 시스템이 매일 자정마다 적용돼
그리고 승격기준은 상대적 점수.
예를들어 A랭크에 해당하는 점수 300점의 사람이 있고
B랭크에 해당하는 점수 290점의 사람이 있는데
B랭크에 해당하는 290점의 사람이 점수를 올려서
301점으로 만든다고 해도 바로 A랭크로 가지는 않고, 자정이 지나야 A랭크로 승격하는 식이야.
그리고 A랭크에는 1000위까지만 얻을 수 있고, B랭크는 기본랭크야
그리고 승격시스템은 자정마다 적용되지만
같은 랭크에 해당하는 사람끼리는 실시간으로 적용돼
예를들어 B랭크의 점수 250점인 사람이 1005위라고하자
B랭크의 점수 249점인 사람이 1006위라고 하고.
만약에 B랭크에 있는 점수 249점이 점수를 올려 251점으로 올린다고하면
자정이 지나지 않아도 1005위보단 높은 순위로 적용돼. a랭크,b랭크승격하고는 다른시스템으로..
그리고 점수가 같을수도 있는데 점수가 같으면 그냥 가나다순으로 랭크를 줄세운다고 할게.
A랭크에 해당하는 1000위의 점수가 300점이고 900위의점수는 350점이야
B랭크에 해당하는사람들이 현재 A랭크에 해당하는 사람들중 일부보다 점수가 높은데,350점보다 높지는 않아.
그리고 A랭크에 해당하는 900위부터 1000위까지의 점수들이 모두 제공되어있고
B랭크에 해당하는 1001위부터 점수 300점이상까지의 순위들의 점수가 모두제공되어 있다고 할게
그럼 B랭크에 해당하는사람중 누구누구까지 1000위권의 a랭크까지 도달하는지 알려면,
일일이 다 점수를 대조하여 세보는 방법외에 효율적인 알고리즘은 없는거야?
길게 써놨지만 1. A는 점수의 배열로 원소수는 1000개, 2. B'은 점수의 배열로 A의 가장 작은 원소보다는 큰 원소들의 집합 일때 3. A 합집합 B'의 1000번째 원소를 구하여라. 맞지?
컴퓨터로 한다면 A랑 B' 을 그냥 합집합하고 돌려도 1000개는 1ms컷이니까 그냥 1000등 검사하면 되고, 손으로 한다면 다음의 binary cut으로 하면 됨. 우선 B의 1등을 뽑아서 걔의 A안에서 등수를 찾으먼 b1의 합산등수 = a안에서의 등수 가 됨
그다음 b1d이 예를들어 a안에서 800등이었다 치면 b1의 통합등수는 800등이고, B'의 원소수가 150개였다 치면 A의 801등-1000등 원소, B'의 1-150등 사이에 답이 있는거지
각 집합을 계속 반씩 짜르는데, 두 집합의 크기중 큰걸 먼저 짜르면 O(log(A+B))가 보장됨. 지금은 A쪽이 더 크니까 A의 900등을 뽑아서 걔가 B에서 예를들어 120등이었다 치면, A의 등수는 1019등이 됨. 1000등은 그거보다 앞에 있느니까 A'을 A의 800-900등 집합으로, B'을 1-120등 집합으로 두고, 이번엔 B의 60을가지고
같은거 반복해나가면 됨.