10/21 (토) (진행중)스트림에서 중위값 찾기 TIL

공부한 것

LeetCode #295. Find Median from Data Stream

⇒ 난이도 Hard여서 그런지, 이진 탐색 트리 구현 후 중위 순회로 중위값을 찾는 전략이 실행 시간 초과로 실패했다.

시간 복잡도 구해보기:

두 메소드 중 addNum()은 시간복잡도가 O(log(N!)), findMedium은 O(N/2)이다. log(N!)은 대략 Nlog(N)으로 볼 수 있으므로 전체 시간 복잡도는 O(Nlog(N))으로 볼 수 있다.

시간 복잡도	시나리오 1: addNum()을 5만 번 호출 후 findMedium()을 1번 호출	시나리오 2: addNum()을 1번 호출하고 findMedium()을 5만 번 호출
전략1: 이진 탐색 트리 구축 후 중위 순회	O(N log(N) + N/2)	O(log(N) + N(N/2)) = O(N^2)
전략2: findMedium()에서 sort() 이용	O(N log(N))	O(N + ?)

풀이 코드:

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(value: number) {
        this.val = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    root: TreeNode | null;
    length: number; 
    constructor() {
        this.root = null;
        this.length = 0;
    }

    // 이진 탐색 트리에 새로운 노드를 삽입
    insert(value: number): void {
        const node = new TreeNode(value);
        if (!this.root) 
            this.root = node;
        else this.insertNode(this.root, node);
        this.length++;
    }

    // 재귀적으로 노드를 삽입하는 도우미 함수
    private insertNode(node: TreeNode, newNode: TreeNode): void {
        // 새로운 노드가 지금 살피는 노드보다 작으면 지금 노드의 왼 자식을 채우고, 왼 자식이 이미 차 있다면 그 왼 자식에 대해 다시 재귀호출해서 알맞은 자리를 탐색한다.
        if (newNode.val < node.val) {
            if (!node.left)
                node.left = newNode;
            else
                this.insertNode(node.left, newNode);
        } else {
            if (!node.right)
                node.right = newNode;
            else
                this.insertNode(node.right, newNode);
        }
    }
}

class MedianFinder {
    private tree: BinarySearchTree;
    constructor() {
        this.tree = new BinarySearchTree();
    }

    addNum(num: number): void {
        this.tree.insert(num);
    }

    findMedian(): number {
        // 이진 탐색 트리를 중위순회하다가 result에 담긴 개수가 반절이 되는 순간 마지막 result 요소를 반환하기.
        // 전체 개수가 홀수일 때: i=(전체 개수 / 2)내림. => result 배열 길이가 i+1개가 되었을 때 result[i]를 반환한다.  
        // 전체 개수가 짝수일 때: i= (전체 개수 / 2 - 1), i+1 = 전체 개수 / 2. => result 배열 길이가 i+2개가 되었을 때 result[i]+result[i+1]를 2로 나눈 값을 반환한다. 
        // if (!this.tree) return 0;
        const resultMap: Map<TreeNode, number> = new Map();
        const stack: TreeNode[] = [this.tree.root];

        while (stack.length) {
            const node = stack[stack.length - 1];
            
            if (node.left && !resultMap.has(node.left)) {
                stack.push(node.left);
            } else {
                resultMap.set(node, node.val);
                // 전체 5개 => 3개가 찼을 때 멈춤
                // 전체 6개 => 4개가 찼을 때 멈춤
                // = 전체 / 2를 내림하고 +1한 값
                const stopMoment = Math.floor(this.tree.length / 2) + 1 
                if (resultMap.size === stopMoment) {
                    const result = [...resultMap.values()];    
                    if (this.tree.length % 2 === 1) return result[stopMoment - 1];
                    else return (result[stopMoment - 2] + result[stopMoment - 1]) / 2;
                }

                stack.pop();
                node.right && stack.push(node.right);
            }
        }
    }
}

Uploaded by N2T

공부한 것

티스토리툴바