2070. Most Beautiful Item for Each Query

2070. Most Beautiful Item for Each Query
Solved
Medium
Topics
Companies
Hint
You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the jth query.

---

접근

 

price 와 beauty 값으로 이뤄진 item 들에서 주어진 query ( 최대 price ) 를 만족하는 최대 beauty 값을 찾는 문제입니다.

주어진 price 를 만족하는 최대 beauty 는 동일 price 에서 가장 큰 beauty 값을 사용하면 되지만 주어지지 않은 price 보다 작은 인접 값 ( item 의 price ) 을 찾는 과정이 중요합니다.

일반적으로 query 별 price 의 순회를 사용하면 O ( N ^ 2 ) 를 사용하게 되므로, Binary Search 를 사용하여 O ( logN ) 을 사용해야 합니다.

 

아래 코드는 Blanced Binary Tree 를 사용했지만 문제는 left, right 를 움직이며 mid 를 찾는 Binary Search 로 충분합니다.

---

코드

/**
 * @param {number[][]} items
 * @param {number[]} queries
 * @return {number[]}
 */
var maximumBeauty = function (items, queries) {
    class Node {
        constructor(value) {
            this.value = value;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }

    class AVLTree {
        constructor() {
            this.root = null;
        }

        // get the height of a node 
        height(node) {
            if (!node) return 0;
            return node.height;
        }

        // get the balance factor of a node 
        balanceFactor(node) {
            if (!node) return 0;
            return this.height(node.left) - this.height(node.right);
        }

        // perform a right rotation 
        rotateRight(node) {
            const leftNode = node.left;
            const rightOfLeftNode = leftNode.right;

            leftNode.right = node;
            node.left = rightOfLeftNode;

            node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
            leftNode.height =
                Math.max(this.height(leftNode.left), this.height(leftNode.right)) + 1;

            return leftNode;
        }

        // perform a left rotation 
        rotateLeft(node) {
            const rightNode = node.right;
            const leftOfRightNode = rightNode.left;

            rightNode.left = node;
            node.right = leftOfRightNode;

            node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
            rightNode.height =
                Math.max(this.height(rightNode.left), this.height(rightNode.right)) + 1;

            return rightNode;
        }

        // insert a new node 
        insert(value) {
            this.root = this.insertNode(this.root, value);
        }

        insertNode(node, value) {
            if (!node) {
                return new Node(value);
            }

            if (value < node.value) {
                node.left = this.insertNode(node.left, value);
            } else if (value > node.value) {
                node.right = this.insertNode(node.right, value);
            } else {
                return node; // duplicate values are not allowed 
            }

            node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;

            const balance = this.balanceFactor(node);

            if (balance > 1 && value < node.left.value) {
                return this.rotateRight(node);
            }

            if (balance > 1 && value > node.left.value) {
                node.left = this.rotateLeft(node.left);
                return this.rotateRight(node);
            }

            if (balance < -1 && value > node.right.value) {
                return this.rotateLeft(node);
            }

            if (balance < -1 && value < node.right.value) {
                node.right = this.rotateRight(node.right);
                return this.rotateLeft(node);
            }

            return node;
        }

        // search for a node 
        search(value) {
            return this.searchNode(this.root, value);
        }

        searchNode(node, value) {
            if (!node) return null;

            if (value < node.value) {
                return this.searchNode(node.left, value);
            } else if (value > node.value) {
                var found = this.searchNode(node.right, value);
                // hack
                if (found === null) return node;
                return found;
            } else {
                return node;
            }
        }
    }

    items.sort((a, b) => {
        if (a[0] > b[0]) {
            return 1;
        }
        if (a[0] < b[0]) {
            return -1;
        }
        // a must be equal to b
        return 0;
    })

    var dict = {};
    var max = 0;

    var tree = new AVLTree();
    for (var i = 0; i < items.length; i++) {
        tree.insert(items[i][0]);

        if (max < items[i][1]) {
            max = items[i][1];
        }

        dict[items[i][0]] = max;
    }

    var answer = [];
    for (var i = 0; i < queries.length; i++) {
        var found = tree.search(queries[i]);
        var value = found === null ? 0 : dict[found.value];
        answer.push(value);
    }

    return answer;
};

---

추가 내용

 

처음 문제를 잘못 이해하고 주어진 query 내에서 조합 가능한 가장 큰 beatuty 를 찾는 방법을 작성했습니다.

이는 아래 코드로 DP 를 사용합니다.

/**
 * @param {number[][]} items
 * @param {number[]} queries
 * @return {number[]}
 */
var maximumBeauty = function (items, queries) {
    // [[1,2],[3,2],[2,4],[5,6],[3,5]]
    items.sort((a, b) => {
        if (a[0] > b[0]) {
            return 1;
        }
        if (a[0] < b[0]) {
            return -1;
        }
        // a must be equal to b
        return 0;
    })

    var mx = {};
    for (var i = 0; i < items.length; i++) {
        var [key, value] = items[i];

        Object.keys(mx).forEach(k => {
            var mx_k = parseInt(k);
            var newkey = parseInt(mx_k) + key;
            var newValue = mx[mx_k] + value;

            // update next
            var prevValue = mx[newkey] || 0;
            if (prevValue < newValue) {
                mx[newkey] = newValue;
            }
        })

        // update self
        var prevValue = mx[key] || 0;
        if (prevValue < value) {
            mx[key] = value;
        }
    }

    var answer = [];
    for (var i = 0; i < queries.length; i++) {
        answer.push(mx[queries[i]] || 0);
    }

    return answer;
};

console.log(maximumBeauty([[1, 2], [3, 2], [2, 4], [5, 6], [3, 5]], [1, 2, 3, 4, 5, 6]));