프로그래밍 면접 문제 13: Median of Integer Stream

 

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 문제 12: Reverse Words in a String

 

프로그래밍 면접 질문 13 : 정수 스트림(Stream)에서 메디안( Median, 중간 값) 구하기

정렬되지 않은 정수의 스트림(stream)이 주어지면 주어진 시간에 정렬 된 순서로 중간 요소를 찾습니다. 무작위 순서로 연속적인 숫자의 배열이 주어지며 배열의 길이는 미리 알 수 없습니다. 이 상황에서 주어진 수 들의 중간 값을 효율적으로 찾는 함수를 작성해야 합니다. 중간 값을 여러 번 찾아야 할 수도 있습니다. 다시 상기시켜보면, 메디안은 홀수 길이의 정렬된 배열에서는 중간 요소이며, 배열의 길이가 짝수인 경우에는 중간 요소의 평균을 의미합니다.

이 문제는 자료 구조 문제입니다. 주어진 수 들을 메디안을 효율적으로 구할 수 있는 자료 구조에 넣어서 이 문제를 해결합니다. 가능한 해결 방법을 살펴보겠습니다.

정렬되지 않은 배열에 정수를 삽입 할 수 있으므로, 배열에 숫자를 하나씩 추가합니다. 삽입 복잡도는 O (1)이지만, 이전 게시물에서 설명한 Median of Median 알고리즘을 사용하면 O(N) 시간이 소모됩니다. 하지만, 우리의 목표는 메디안을 가장 효율적으로 찾는 것입니다. 삽입 성능에 대해서는별로 신경 쓰지 않겠습니다. 그러나 이 알고리즘은 정반대의 역할을하기 때문에 정렬되지 않은 배열은 적절한 솔루션이 아닙니다.

정렬 된 배열을 사용하면 어떨가요? 이진 검색을 사용하면 주어진 수를 삽입하는 위치를 찾는데 O(logN) 시간이 소요됩니다. 그리고 메디안 값을 묻는 시점이 언제든, 배열의 길이가 홀수인 경우에는 중간 요소를 반환하고 배열의 길이가 짝수인 경우에는 중간 요소의 평균 값을 반환할 수 있습니다. 이는 정확히 O(1) 시간에 수행할 수 있습니다. 하지만 정렬된 배열을 사용하는 방법에는 큰 단점이 존재합니다. 요소를 삽입한 후에 배열을 정렬된 상태로 유지하려면, 다른 요소들을 오른쪽으로 이동시켜야 하고, 이는 O(N) 시간이 소요됩니다. 따라서, 수를 삽입할 위치를 찾는데 O(logN) 시간이 걸리더라도, 요소의 이동으로 인해 전체 삽입 복잡도는 O(N)이 됩니다. 그러나 메디안을 찾는 방법은 여전히 매우 효율 적이고, 일정한 시간이 소요됩니다. 하지만, 선형 시간 복잡도를 갖는 삽입은 상당히 비효율적이며 더 나은 성능을 가진 알고리즘을 사용하는 것이 좋습니다.

연결 리스트(Linked List)를 사용해 보겠습니다. 먼저, 연결 리스트는 정렬되지 않은 상태입니다. 삽입 복잡도는 O(1)이고, 연결 리스트의 처음(head) 또는 끝(tail)에 수를 삽입할 수 있지만, 정렬되지 않은 배열과 동일한 문제가 있습니다. 메디안을 찾는데 드는 복잡도는 O(N)입니다. 연결 리스트를 정렬된 상태로 유지하면 어떨까요? 연결 리스트의 특정 위치에 대한 삽입 복잡도는 O(1)이기 때문에 지금 까지는 괜찮아 보입니다. 하지만, 정렬이 되어 있다해도 연결 리스트에서 이진 탐색을 수행할 수 없기 때문에, 정렬된 배열에서 삽입할 정확한 위치를 찾는데 드는 복잡도는 O(logN)이 아니라 O(N) 입니다. 따라서 정렬된 연결 리스트를 사용하는 방법은 삽입에 O(N), 메디안을 찾는데 O(1), 즉 정렬된 배열과 동일하기 때문에 노력할 만한 가치가 없다고 할 수 있습니다. 정렬된 배열 삽입에서는 요소들의 이동으로 인해서 선형 복잡도를 가지며, 연결 리스트에서 이진 탐색을 할 수 없기 때문에 이 역시 선형 복잡도를 갖습니다. 이는 항상 우리가 염두해 두어야 할 매우 기본적인 자료 구조에 대한 지식입니다.

스택이나 큐를 사용하는 것은 도움이되지 않습니다. 삽입은 O(1)이지만, 메디안을 찾는데 O(N)의 복잡도를 갖게되고이는 매우 비효율적입니다.

트리를 사용하면 어떨까요? 이진 검색 트리를 이용해 각 노드에서 추가 정보와 함께 왼쪽 및 오른쪽 하위 트리의 자식의  수를 봅시다. 트리에 전체 노드 수를 기록합니다. 이 추가 정보를 사용해 현재 노드의 왼쪽과 오른쪽에있는 자식 수를 기반으로 트리에서 적절한 가지(branch)를 가져와 O(logN) 시간 안에 메디안을 찾을 수 있습니다. 하지만  표준 이진 검색 트리에서 정렬된 순서로 숫자를 받으면 연결 리스트로 변형이 될 수 있기 때문에 삽입 복잡도는 O(N)입니다.

따라서 표준 이진 검색 트리의 최악의 경우의 동작을 피하기 위해 균형 이진 검색 트리를 사용하겠습니다. 높이 균형 이진 탐색 트리 (즉, AVL 트리)에서, 균형 인자는 왼쪽 및 오른쪽 하위 트리의 높이 간의 차이를 말합니다. 균형 인자 0, +1, -1을 갖는 노드는 균형을 이룬 것으로 간주합니다. 하지만, 사용할 트리에서 균형 요소는 높이가 아닙니다. 왼쪽 하위 트리의 노드 수에서 오른쪽 하위 트리의 노드 수를 뺀 값입니다. +1 또는 0의 균형 계수를 갖는 노드만 균형 잡힌 것으로 간주합니다. 따라서 왼쪽 하위 트리의 노드 수는 오른쪽 하위 트리의 노드 수와 같거나 하나 많고 작지 않습니다. 트리의 모든 노드에서 이 균형 요소를 확인하면 요소 수가 홀수인 경우 트리의 루트가 메디안입니다. 짝수의 경우, 메디안은 루트와 그 하위의 하위 트리 인 inorder 자식의 평균 값입니다. 따라서 균형 상태를 유지하는 삽입의 복잡성은 O(logN)이며, 노드 수가 짝수일 경우 삽입 할 때마다 루트의 inorder 자식을 계산한다고 가정하면 메디안 연산은 O(1)입니다. 삽입 및 균형 조정은 AVL 트리와 매우 유사합니다. 높이를 업데이트하는 대신 노드 정보의 수를 업데이트합니다.

균형 이진 검색 트리가 삽입의 복잡도는 O(logN)이고 메디안 찾는 과정의 복잡도는 O(1)이기 때문에, 최적의 솔루션 인 것 같습니다.  더 나아질 수 있을까요? 동일한 복잡성을 갖는, 보다 단순하고 우아한 솔루션을 만들어낼 수 있습니다. 2가지 요구사항을 갖는 최대 힙(heap)과 최소 힙(heap) 이렇게 두 개 힙을 사용합니다. 첫 번째 요구사항은 수의 그룹을 반으로 나눌 때 가장 작은 수들을 최대 힙에 넣고, 가장 큰 수들을 최소 힙에 넣습니다. 따라서 최대 힙 내의 요소는 최소 힙 내의 요소보다 항상 작거나 같습니다. 이를 순서 요구사항이라 부르겠습니다. 두 번째 요구사항은 최대 힙 내 요소의 수가 최소 힙 내 요소의 수와 같거나 1개 많은 것입니다. 따라서, 지금까지 2N 개의 요소(짝수)를 받은 경우, 최대 힙과 최소 힙은 모두 N개의 요소를 포함하게 됩니다. 반대로 2N + 1개의 요소(홀수)를 받은 경우 최대 힙에는 N + 1개의 요소가 최소 힙에는 N개의 요소가 포함됩니다. 이를 크기 요구사항이라 부르겠습니다.

힙은 위의 두 가지 요구사항을 고려해서 구성됩니다. 그런 다음 메디안을 요청 받았을 때, 받은 요소의 수가 홀수인 경우, 최대 힙의 루트가 메디안이 됩니다. 받은 요소의 수가 짝수인 경우, 최대 힙과 최소 힙의 루트를 더한 값의 평균 값이 메디안이 됩니다. 이제 이 접근 방법이 동작하는 이유와 힙을 구성하는 방법을 분석해 보겠습니다.

두 개의 메소드를 작성할 예정인데, 하나는 새로 전달 받은 수를 힙에 삽입하는 메소드고, 다른 하나는 메디안을 구하는 메소드입니다. 삽입 과정은 두 가지 요구사항을 고려해서 새로 요소를 받을 때마다 실행합니다. 요소를 힙에 삽입하기 전에, 전체 요소의 수가 홀수인지 짝수인지 여부에 따라 두 가지 접근 방법을 사용할 예정입니다.

먼저 삽입 과정에서의 크기 요구사항을 분석해 보겠습니다. 두 경우 모두 최대 힙에 새 요소를 삽입하지만, 그 뒤의 수행 방법에는 차이가 있을 수 있습니다. 첫 번째 경우 삽입하기 전에 힙 내의 전체 요소의 수가 짝수이면, 최대 힙과 최소 힙의 요소의 수는 크기 요구사항으로 인해 모두 N입니다. 최대 힙에 요소를 새로 삽입한 후에는 힙 내의 요소의 수가 N + 1이 되지만 크기 요구사항을 위반하지 않습니다. 최대 힙은 최소 힙보다 1개 더 요소를 포함할 수 있습니다. 최대 힙에 요소를 새로 삽입하면 힙 내 요소의 수는 N + 2가 됩니다. 하지만 이는 최대 힙의 요소의 수가 최소 힙의 요소의 수 보다 하나 더 클 수 있다는, 크기 요구사항을 위반합니다. 따라서 최대 힙에서 요소를 하나 빼내고 이를 최소 힙에 삽입합니다. 자세한 내용은 곧 설명하겠습니다.

이제 순서 요구사항을 분석해 보겠습니다. 이 요구사항은 최대 힙 내의 모든 요소가 최소 힙의 모든 요소보다 작거나 같아야 한다는 내용의 요구사항입니다. 따라서 최대 힙에는 수 그룹을 절반으로 나눴을 때 가장 작은 수들이 포함되고, 최소 힙에는 가장 큰 수들이 포함됩니다. 이런 의도로 인해 최대 힙의 루트(root)는 작은 값들 중에서 가장 큰 값이되며, 최소 힙의 루트는 큰 값들 중에서 가장 작은 값이 됩니다. 이를 염두해두어 삽입을 수행하기 전에, 전체 요소의 수가 짝수인지 홀수인지에 따라 두 가지 방법을 사용합니다. 짝수의 경우 최대 힙에 요소를 새로 삽입합니다. 새 요소가 최소 힙의 모든 요소보다 작거나 같으면 순서 요구사항에 만족하기 때문에 문제가 없습니다. 이 비교 작업은 최소 힙의 루트가 힙의 최소 값이기 때문에 루트와 비교를 통해서 할 수 있고, 이는 O(1)의 시간 복잡도를 갖습니다. 하지만 새 요소가 최소 힙의 루트보다 크면 순서 요구사항에 맞춰 해당 요소들을 교환해야 합니다. 이 경우 최대 힙의 루트 값이 새 요소가 됩니다. 따라서 최소 힙의 루트를 빼내서 최대 힙에 삽입합니다. 또한 최대 힙의 루트를 빼내 최소 힙에 삽입합니다. 두 번째 경우, 삽입하기 전에 전체 요소의 수가 홀수이면 최대 힙에 새 요소를 삽입한 다음, 최대 힙에서 요소 하나를 빼내 최소 힙에 넣습니다. 순서 요구사항을 만족시키기 위해 최대 힙 내 요소 중에서 최대 값을 갖는 요소 즉, 루트를 빼내 최소 힙에 삽입합니다. 삽입 과정의 복잡도는 힙의 삽입 복잡도인 O(logN)입니다.

지금까지 설명한 내용이 바로 삽입 절차가 처리되는 과정입니다. 삽입을 진행하면서 크기와 순서 요구사항을 충족시키기 위한 작업을 했습니다. 메디안을 찾는 기능은 다음과 같습니다. 어느 시점에서든 메디안을 찾는 요청을 받을 수 있습니다. 해당 시점에 전체 요소의 수가 홀수이면, 메디안은 최대 힙의 루트입니다. 예제를 통해 이를 시각화 해보겠습니다. 현재까지 7개의 요소를 받았다고 가정하면, 정렬된 순서에서 메디안은 4번째 수입니다. 위에서 설명한 요구사항에 의해, 현재 최대 힙에는 4개의 가장 작은 수들이 포함되어 있고, 최소 힙에는 가장 큰 수들이 포함되어 있습니다.최대 힙의 루트는 가장 작은 4개의 요소들 중에서 가장 큰 수이기 때문에, 정렬된 순서에서 4번째 수가 되며, 이 수가 바로 메디안 값입니다. 반면 전체 요소의 수가 짝수이면, 최대 힙의 루트와 최소 힙의 루트의 평균 값이 메디안입니다. 8개의 수를 받았다고 가정하면, 정렬된 순서에서 4번째 5번째 수를 더한 다음 평균을 낸 값이 메디안입니다. 현재, 최대 힙과 최소 힙에는 모두 4개의 요소가 포함되어 있습니다. 최대 힙의 루트는 가장 작은 수들 중에서 가장 큰 수이며, 이는 정렬된 순서에서 4번째 수입니다. 그리고 최소 힙의 루트는 가장 큰 수들 중에서 최소 값이며, 이는 정렬된 순서에서 5번째 수가 됩니다. 따라서, 메디안은 루트들의 평균 값입니다. 두 경우 모두에서 삽입이나 제거가 수행되지 않고 힙의 루트에 바로 접근하기 때문에, 메디안을 구하는 시간 복잡도는 O(1)입니다. 그러므로, 전체적으로 이 솔루션은 힙을 찾는데 O(1) 삽입에 O(logN)의 시간 복잡도를 갖습니다.

실제 코드가 100마디 말보다 낫습니다. 다음 코드는 2개의 힙을 이용한 해결방법 입니다. 보시다시피, 설명한 것보다 훨씬 덜 복잡합니다. 최소 힙의 구현만 제공하는, 파이썬의 heapq 모듈을 사용할 수 있습니다. 하지만 최대 힙 또한 필요하기 때문에, 삽입할 수에 -1을 곱한 다음 삽입하면 최소 힙을 최대 힙처럼 동작하게 만들 수 있습니다. 따라서, 최대 힙에 삽입하거나 접근할 때마다 원래 수에서 -1을 곱합니다.

class streamMedian:
    def __init__(self):
        self.minHeap, self.maxHeap = [], []
        self.N=0
 
    def insert(self, num):
        if self.N%2==0:
            heapq.heappush(self.maxHeap, -1*num)
            self.N+=1
            if len(self.minHeap)==0:
                return
            if -1*self.maxHeap[0]>self.minHeap[0]:
                toMin=-1*heapq.heappop(self.maxHeap)
                toMax=heapq.heappop(self.minHeap)
                heapq.heappush(self.maxHeap, -1*toMax)
                heapq.heappush(self.minHeap, toMin)
        else:
            toMin=-1*heapq.heappushpop(self.maxHeap, -1*num)
            heapq.heappush(self.minHeap, toMin)
            self.N+=1
 
    def getMedian(self):
        if self.N%2==0:
            return (-1*self.maxHeap[0]+self.minHeap[0])/2.0
        else:
            return -1*self.maxHeap[0]

streamMedian이라는 클래스가 있고, 새로운 요소를 받을 때마다 insert 함수가 호출됩니다. getMedian 함수를 이용해 메디안 값을 얻습니다.

이 문제는 절요한 방식으로 자료 구조의 기본 개념을 테스트하는 문제이기 때문에 훌륭한 면접 문자라고 할 수 있습니다.

 

다음글 – 프로그래밍 면접 문제 14: Check Balanced Parentheses