10.10 스트림에서의 순위

문제 

정수 스트림을 읽는다고 하자. 주기적으로 어떤 수 x의 랭킹(x보다 같거나 작은 수의 갯수)를 확인하고 싶다. 해당 연산을 지원하는 자료구조와 알고리즘을 구현하라. 수 하나를 읽을 때마다 호출되는 메서드 track(int x)와, x보다 작거나 같은 수의 갯수( x자신을 제외)를 반환하는 메서드 getRankOfNumber(int x)를 구현하라

 

입력 : 5,1,4,4,5,9,7,13,3

출력 :  getRankOfNumber(1) = 0

 getRankOfNumber(3 ) = 1

 getRankOfNumber(4 ) = 3

 

해법

모든 원소를 정렬된 상태로 보관하는 배열을 사용하면 구현하기가 상대적으로 간단해진다.

새로운 원소를 삽입할때마다 다른 원소들을 옆으로 옮겨 공간을 확보해야하는데 그렇다보면 track() 호출시 효율성이 떨어진다. 원소간의 상대적 순서를 유지할 수 있으면서도 새로운 원소를 삽입하기에 도 효율적인 자료구조가 필요하다 -> 이진 탐색 트리가 적당할 것같다.

 

원소들을 배열에 보관하는 대신 이진 탐색 트리에 삽입하며 track()은 O(logN)시간에 가능하고, 각 노드가 자신의 왼쪽에 있는 자식 노드의 수를 알고있도록 하면 중위 탐색을 모두 하지 않고도 최소한의 탐색으로 랭킹을 확인할 수 있을 것이다.

이런식으로 트리가 구성되어 있다고 가정해보자 그러면 만약 24의 랭킹은 어떻게 구할 수 있을까? 

각 노드의 옆에 있는 작은 숫자는 왼쪽 노드의 갯수이다. 루트 20과 24를 비교해보면 24는 오른쪽에 있어야 하기때문에 20의 왼쪽 노드의 갯수인 4 + 1 (20을 포함) = counter은 5개가 된다. 그다음, 25와 비교해보자 24는 25의 왼쪽에 잇어야하므로 갱신하지 않는다.

다음 23과 비교해보자 23보다는 24는 오른쪽에 있어야하므로 23의 왼쪽 노드의 갯수인 0 + 1 (23을 포함) = 1 만큼을 counter에 더해준다.

그다음 오른쪽으로 가면 24와 만나기 때문에 24의 counter인 6을 반환하면 된다.

class Ranknode :
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None
        self.leftcount = 0

    def insert(d):
        if d <= data :
            if self.left is None :
                self.left = Node(d)
            else :
                self.left.insert(d)
            leftcount +=1
        else :
            if self.right is None :
                self.right = Node(d)
            else :
                self.right.insert(d)

    def getRank(d):
        if d == self.data :
            return leftcount
        elif d < self.data :
            if self.left is None :
                return -1
            else :
                self.left.getRank(d)
        else :
            rightrank = right.getRank(d) if self.right is not None else -1
            if rightrank == -1 :
                return -1
            else :
                return leftcount + 1 + rightrank


Root = None

def track(number):
    if Root is None :
        Root = Ranknode(number)
    else :
        Root.insert(number)

def getRank(number):
    return Root.getRank(number)