짬뽕얼큰하게의 맨땅에 헤딩 :: '분류 전체보기' 카테고리의 글 목록 (15 Page)

Most Beautiful Item for Each Query

알고리즘 2025. 2. 21. 08:59

Leetcode Problem:

Summary

  • Given a 2D integer array of item prices and beauties, and a 0-indexed integer array of queries, determine the maximum beauty of an item whose price is less than or equal to each query.

Approach

  • The solution uses a modified merge sort algorithm to sort the items based on their prices
  • Then, it iterates over the sorted items and updates the beauty of each item if its price is less than the current query
  • Finally, it uses a binary search approach to find the maximum beauty for each query.

Complexity

  • O(n log n + m log n), where n is the number of items and m is the number of queries.

Explanation

  • The modified merge sort algorithm sorts the items based on their prices and then updates the beauty of each item if its price is less than the current query
  • This is done to ensure that the items are sorted in ascending order of their prices
  • The binary search approach is used to find the maximum beauty for each query by finding the first item whose price is greater than the query and returning its beauty.

Solution Code:


struct _item{
    int price;
    int beauty;
};

class Solution {
public:
    _item arr[100001];
    _item tmp[100001];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = l;
        while(i <= mid & j <= r){
            if(arr[i].price < arr[j].price){
                tmp[cur++] = arr[i++];
            } else if (arr[i].price > arr[j].price){
                tmp[cur++] = arr[j++];
            } else{
                if(arr[i].beauty >= arr[j].beauty){
                    tmp[cur++] = arr[i++];
                } else {
                    tmp[cur++] = arr[j++];
                }
            }
        }
        while(i<= mid){
            tmp[cur++] = arr[i++];
        }
        for(i = l; i < cur; i++){
            arr[i] = tmp[i];
        }
    }
    void merge_sort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid+1, r);
        merge(l, mid, r);
    }
    vector maximumBeauty(vector>& items, vector& queries) {
        for(int i = 0 ; i < items.size(); i++){
            arr[i].price = items[i][0];
            arr[i].beauty = items[i][1];
        }
        merge_sort(0, items.size() - 1);
        int maxBeauty = arr[0].beauty;
        for(int i = 1 ; i < items.size(); i++){
            if(arr[i].beauty < maxBeauty){
                arr[i].beauty = maxBeauty;
            } else {
                maxBeauty = arr[i].beauty;
            }
        }
        vector ansV;
        for(int i = 0 ; i < queries.size(); i++){
            int l = 0;
            int r = items.size() - 1;
            int ans = 0;
            while(l <= r){
                int mid = (l + r ) / 2;
                if (arr[mid].price > queries[i]){
                    r = mid - 1;
                    continue;
                }
                ans = arr[mid].beauty;
                l = mid + 1;
            }
            ansV.push_back(ans);
        }
        return ansV;
    }
};

'알고리즘' 카테고리의 다른 글

Minimized Maximum of Products Distributed to Any Store  (0) 2025.02.21
Count the Number of Fair Pairs  (0) 2025.02.21
Prime Subtraction Operation  (0) 2025.02.21
Shortest Subarray With OR at Least K II  (0) 2025.02.21
Minimum Array End  (0) 2025.02.21
블로그 이미지

짬뽕얼큰하게

,

Prime Subtraction Operation

알고리즘 2025. 2. 21. 08:55

Leetcode Problem:

Summary

  • Given a 0-indexed integer array, determine if it can be made a strictly increasing array by subtracting prime numbers from its elements.

Approach

  • The approach involves first creating a boolean array to store the primality of numbers from 2 to 1000
  • Then, for each number in the input array, we try to subtract the smallest prime that is less than the number from it
  • If the resulting number is less than the previous number, we return false
  • Otherwise, we continue with the next number
  • If we can successfully make the array strictly increasing, we return true.

Complexity

  • O(n * sqrt(1000))

Explanation

  • The time complexity is O(n * sqrt(1000)) because for each number in the input array, we try to subtract the smallest prime that is less than the number from it
  • The outer loop runs n times, and the inner loop runs up to sqrt(1000) times
  • The space complexity is O(1000) because we need to store the primality of numbers from 2 to 1000 in the boolean array.

Solution Code:


class Solution {
public:
    bool isPrime[1001];
    bool primeSubOperation(vector& nums) {
        for(int i = 2 ; i <= 1000; i++){
            isPrime[i] = true;
        }
        for(int i = 2; i*i <= 1000; i++){
            for(int j = 2; i*j <= 1000; j++){
                isPrime[i*j] = false;
            }
        }
        for(int i = nums[0] - 1; i >= 2; i--){
            if(isPrime[i]){
                nums[0] -= i;
                break;
            }
        }
        for(int i = 1; i < nums.size(); i++){
            for(int j = nums[i] - 1; j >= 2; j--){
                if(isPrime[j] && nums[i-1] < (nums[i] - j)){
                    nums[i] -= j;
                    break;
                }
            }
            if(nums[i-1] >= nums[i]) return false;
        }

        return true;
    }
};

'알고리즘' 카테고리의 다른 글

Count the Number of Fair Pairs  (0) 2025.02.21
Most Beautiful Item for Each Query  (0) 2025.02.21
Shortest Subarray With OR at Least K II  (0) 2025.02.21
Minimum Array End  (0) 2025.02.21
Maximum XOR for Each Query  (0) 2025.02.21
블로그 이미지

짬뽕얼큰하게

,

Shortest Subarray With OR at Least K II

알고리즘 2025. 2. 21. 08:52

Leetcode Problem:

Summary

  • The problem requires finding the length of the shortest special subarray in the given array of non-negative integers and an integer k
  • A special subarray is defined as an array where the bitwise OR of all its elements is at least k.

Approach

  • The approach used is to use a bit manipulation technique to efficiently calculate the bitwise OR of all subarrays
  • A custom _bit struct is created to store the count of 1s in the binary representation of each number
  • The add and sub methods are used to update the count of 1s in the _bit struct
  • The getNum method is used to calculate the bitwise OR of all numbers in the subarray
  • The minimumSubarrayLength function uses two pointers to traverse the array and update the _bit struct accordingly
  • If the bitwise OR of the subarray is greater than or equal to k, the length of the subarray is updated
  • The function returns the length of the shortest special subarray or -1 if no special subarray exists.

Complexity

  • O(n log n) due to the getNum method, where n is the size of the input array
  • The add and sub methods are O(log n) and are called in a loop, so the overall time complexity is O(n log n)
  • The space complexity is O(1) as the _bit struct only uses a constant amount of space.

Explanation

  • The solution code first creates a custom _bit struct to store the count of 1s in the binary representation of each number
  • The add and sub methods are used to update the count of 1s in the _bit struct
  • The getNum method is used to calculate the bitwise OR of all numbers in the subarray
  • The minimumSubarrayLength function uses two pointers to traverse the array and update the _bit struct accordingly
  • If the bitwise OR of the subarray is greater than or equal to k, the length of the subarray is updated
  • The function returns the length of the shortest special subarray or -1 if no special subarray exists.

Solution Code:


struct _bit{
    int cnt[32] = {0};
    void add(int num){
        int c = 0;
        while(num){
            if (num%2){
                cnt[c]++;
            }
            num /= 2;
            c++;
        }
    }
    void sub(int num){
        int c = 0;
        while(num){
            if (num %2){
                cnt[c]--;
            }
            num /= 2;
            c++;
        }
    }
    int getNum(){
        long long pow = 1;
        long long num = 0;
        for(int i = 0 ; i < 31; i++){
            int x = 0;
            if(cnt[i] > 0){
                x = 1;
            }
            num += pow * x;
            pow *= 2;
        }
        return num;
    }
};


class Solution {
public:
    _bit b;
    int minimumSubarrayLength(vector& nums, int k) {
        int res = nums.size()+1;
        
        int l = 0;
        int r = 0;
        if (k == 0 ) return 1;
        while(r < nums.size() && l <= r){
            int num = b.getNum();
            if(num >= k){
                res = min(res, r - l);
                b.sub(nums[l++]);
            } else {
                b.add(nums[r++]);
            }
        }
        int num = b.getNum();
        if(num >= k){
            res = min(res, r - l);
        } 
        while(l < nums.size()){
            num = b.getNum();
            if(num >= k){
                res = min(res, r - l);
                b.sub(nums[l++]);
            } else {
                break;
            }
        }
        
        if (res == nums.size() + 1) return -1;
        return res;
    }
};

'알고리즘' 카테고리의 다른 글

Most Beautiful Item for Each Query  (0) 2025.02.21
Prime Subtraction Operation  (0) 2025.02.21
Minimum Array End  (0) 2025.02.21
Maximum XOR for Each Query  (0) 2025.02.21
Largest Combination With Bitwise AND Greater Than Zero  (0) 2025.02.21
블로그 이미지

짬뽕얼큰하게

,

Minimum Array End

알고리즘 2025. 2. 21. 08:47

Leetcode Problem:

Summary

  • Construct an array of positive integers where the result of the bitwise AND operation between all elements is given, and the array is strictly increasing.

Approach

  • The approach is to create two arrays, one for the given x and one for the given n
  • We then iterate through the arrays and construct the result array
  • If the current bit in x is 1, we add 1 to the result array
  • If the current bit in x is 0, we add the next available number from the array n
  • We then calculate the final result by summing up the product of each number in the result array and its corresponding power of 2.

Complexity

  • O(log n + log x) = O(log (max(n, x)))

Explanation

  • The solution iterates through the arrays x and n, constructing the result array
  • It uses two arrays to store the current bit in x and the next available number from n
  • The time complexity is O(log (max(n, x))) because we iterate through the arrays x and n, and each iteration takes constant time
  • The space complexity is also O(log (max(n, x))) because we store the result array and the two input arrays.

Solution Code:


class Solution {
public:
    vector xv, nv, ansv;
    long long minEnd(int n, int x) {
        n--;
        while(n){
            nv.push_back(n%2);
            n /= 2;
        }
        while(x){
            xv.push_back(x%2);
            x /= 2;
        }
        int nIdx = 0;
        for(int xIdx = 0; xIdx < xv.size(); xIdx++){
            if(xv[xIdx] == 1){
                ansv.push_back(1);
            } else{
                if(nIdx < nv.size()){
                    ansv.push_back(nv[nIdx++]);
                } else{
                    ansv.push_back(0);
                }
            }
        }
        while(nIdx < nv.size()){
            ansv.push_back(nv[nIdx++]);
        }
        long long ans = 0;
        long long pow = 1;
        for(int i = 0 ; i < ansv.size(); i++){
            ans += pow*ansv[i];
            pow *= 2;
        }

        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Prime Subtraction Operation  (0) 2025.02.21
Shortest Subarray With OR at Least K II  (0) 2025.02.21
Maximum XOR for Each Query  (0) 2025.02.21
Largest Combination With Bitwise AND Greater Than Zero  (0) 2025.02.21
Find if Array Can Be Sorted  (0) 2025.02.21
블로그 이미지

짬뽕얼큰하게

,

Maximum XOR for Each Query

알고리즘 2025. 2. 21. 08:44

Leetcode Problem:

Summary

  • Given a sorted array of non-negative integers and an integer maximumBit, find the maximum XOR value for each query and return the answers.

Approach

  • The solution uses the XOR operation to find the maximum XOR value for each query
  • It initializes the accumulator with the XOR of all numbers in the array, then iterates through the array from right to left, updating the accumulator with the XOR of the current number and the maximum possible XOR value
  • The result is the XOR of the accumulator and the maximum possible XOR value, which is the maximum XOR value for the current query.

Complexity

  • O(n) where n is the number of elements in the array, as it only requires a single pass through the array.

Explanation

  • The solution starts by initializing the accumulator with the XOR of all numbers in the array
  • This is done to ensure that the maximum XOR value for the first query is correctly calculated
  • Then, it iterates through the array from right to left, updating the accumulator with the XOR of the current number and the maximum possible XOR value
  • The result is the XOR of the accumulator and the maximum possible XOR value, which is the maximum XOR value for the current query
  • This process is repeated for each query, and the results are stored in the result vector.

Solution Code:


class Solution {
public:
    vector getMaximumXor(vector& nums, int maximumBit) {
        int max_num = (1 << maximumBit) - 1;
        vector res;
        int acc = 0;
        for(int i = 0 ; i < nums.size(); i++) {
            acc ^= nums[i];
        }

        for(int i = nums.size()-1; i>= 0; i--) {
            res.push_back(acc ^ max_num);
            acc ^= nums[i];
        }
        return res;
    }
};

'알고리즘' 카테고리의 다른 글

Shortest Subarray With OR at Least K II  (0) 2025.02.21
Minimum Array End  (0) 2025.02.21
Largest Combination With Bitwise AND Greater Than Zero  (0) 2025.02.21
Find if Array Can Be Sorted  (0) 2025.02.21
Find Unique Binary String  (0) 2025.02.20
블로그 이미지

짬뽕얼큰하게

,

Largest Combination With Bitwise AND Greater Than Zero

알고리즘 2025. 2. 21. 08:40

Leetcode Problem:

Summary

  • Find the size of the largest combination of elements in the candidates array with a bitwise AND greater than 0.

Approach

  • The approach used is to generate all possible combinations of elements in the candidates array by iterating over all possible bitmasks (0-24)
  • For each bitmask, count the number of elements in the candidates array that have the corresponding bit set
  • The maximum count is the size of the largest combination with a bitwise AND greater than 0.

Complexity

  • O(n * 24) where n is the number of elements in the candidates array

Explanation

  • The solution iterates over all possible bitmasks (0-24) and for each bitmask, it counts the number of elements in the candidates array that have the corresponding bit set
  • This is done by using a bitwise AND operation between the bitmask and each element in the candidates array
  • If the result is greater than 0, it means the bit is set in the element, so the count is incremented
  • The maximum count is updated if a larger count is found
  • The solution returns the maximum count as the size of the largest combination with a bitwise AND greater than 0.

Solution Code:


class Solution {
public:
    int largestCombination(vector& candidates) {
        int maxCnt = 0;
        for(int i = 0 ; i < 24; i++){
            int mask = 1 << i;
            int cnt = 0;
            for(int j = 0 ; j < candidates.size(); j++){
                if((candidates[j] & mask) > 0){
                    cnt++;
                }
            }
            maxCnt = max(maxCnt, cnt);
        }
        return maxCnt;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Array End  (0) 2025.02.21
Maximum XOR for Each Query  (0) 2025.02.21
Find if Array Can Be Sorted  (0) 2025.02.21
Find Unique Binary String  (0) 2025.02.20
Minimum Number of Changes to Make Binary String Beautiful  (0) 2025.02.20
블로그 이미지

짬뽕얼큰하게

,

Find if Array Can Be Sorted

알고리즘 2025. 2. 21. 08:37

Leetcode Problem:

Summary

  • Given an array of positive integers, determine if it can be sorted in ascending order by swapping adjacent elements with the same number of set bits.

Approach

  • The solution uses a two-pass approach to track the maximum and minimum numbers encountered so far
  • It also keeps track of the number of set bits for each number
  • If a number with more set bits is found after a number with the same number of set bits, the function returns false
  • If all numbers can be sorted, the function returns true.

Complexity

  • O(n) where n is the number of elements in the array, as each element is visited once.

Explanation

  • The solution works by iterating through the array and tracking the number of set bits for each number
  • If a number with more set bits is found after a number with the same number of set bits, the function returns false
  • If all numbers can be sorted, the function returns true
  • The time complexity is O(n) because each element is visited once, and the space complexity is O(1) because only a constant amount of space is used.

Solution Code:


class Solution {
public:
    int getOneCnt(int num){
        int cnt = 0;
        while(num){
            cnt++;
            num &= num-1;
        }
        return cnt;
    }
    vector arr;
    bool canSortArray(vector& nums) {
        int beforeCnt = getOneCnt(nums[0]);
        int beforeMax = 0;
        int maxNum = nums[0];
        for(int i = 1 ; i < nums.size(); i++){
            int cnt = getOneCnt(nums[i]);
            if( cnt != beforeCnt){
                if(maxNum > nums[i]) return false;
                beforeMax = maxNum;
                maxNum = nums[i];
                beforeCnt = cnt;
                continue;
            }
            if(beforeMax > nums[i]) return false;
            if(maxNum < nums[i]){
                maxNum = nums[i];
            }
        }

        return true;
    }
};

'알고리즘' 카테고리의 다른 글

Maximum XOR for Each Query  (0) 2025.02.21
Largest Combination With Bitwise AND Greater Than Zero  (0) 2025.02.21
Find Unique Binary String  (0) 2025.02.20
Minimum Number of Changes to Make Binary String Beautiful  (0) 2025.02.20
String Compression III  (0) 2025.02.20
블로그 이미지

짬뽕얼큰하게

,

Find Unique Binary String

알고리즘 2025. 2. 20. 21:46

Leetcode Problem:

Summary

  • Given an array of unique binary strings, return a binary string that does not appear in the array.

Approach

  • The solution uses a set data structure to store the binary numbers represented by the input strings
  • It then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set.

Complexity

  • O(2^n * n) where n is the length of the input strings

Explanation

  • The solution first converts each binary string to a decimal number using the `makeNum` function
  • It then stores these decimal numbers in a set
  • The `makeStr` function is used to convert a decimal number back to a binary string
  • The solution then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set
  • This approach ensures that the solution finds the first binary string that does not appear in the input array.

Solution Code:


class Solution {
public:
    int makeNum(string s){
        int num = 0;
        for(int i = 0 ; i < s.size(); i++){
            num *= 2;
            num += s[i] - '0';
        }
        return num;
    }
    string makeStr(int num, int length){
        string res = "";
        for(int i = 0 ; i < length; i++){
            res = string(1, '0'+(num %2)) + res;
            num /= 2;
        }
        return res;
    }
    bool set[1<<16];
    string findDifferentBinaryString(vector& nums) {
        int length = nums[0].size();
        for(int i = 0 ; i < nums.size(); i++){
            set[makeNum(nums[i])] = true;
        }
        for(int i = 0 ; i < (1 << 16); i++){
            if(set[i]){
                continue;
            }
            return makeStr(i, length);
        }
        return "";
    }
};

'알고리즘' 카테고리의 다른 글

Largest Combination With Bitwise AND Greater Than Zero  (0) 2025.02.21
Find if Array Can Be Sorted  (0) 2025.02.21
Minimum Number of Changes to Make Binary String Beautiful  (0) 2025.02.20
String Compression III  (0) 2025.02.20
Rotate String  (0) 2025.02.20
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Changes to Make Binary String Beautiful

알고리즘 2025. 2. 20. 08:50

Leetcode Problem:

Summary

  • The problem requires to find the minimum number of changes required to make a binary string beautiful
  • A beautiful string is a string that can be partitioned into substrings with even length and only containing 1's or 0's.

Approach

  • The approach is to iterate over the string in steps of 2 and count the number of pairs of characters that are not the same
  • If the pair is not the same, it means that the string needs to be changed to make it beautiful, so we increment the result.

Complexity

  • O(n/2) = O(n), where n is the length of the string.

Explanation

  • The solution iterates over the string in steps of 2, which is because each pair of characters is considered together
  • If the pair of characters is not the same, it means that the string needs to be changed to make it beautiful, so we increment the result
  • The time complexity is O(n) because we are iterating over the string once.

Solution Code:


class Solution {
public:
    int minChanges(string s) {
        int res = 0;
        for(int i = 0 ; i < s.size(); i += 2){
            if ((s[i] == '0' && s[i+1] == '0') || (s[i] == '1' && s[i+1] == '1')){
                continue;
            }
            res++;
        }
        return res;
    }
};

'알고리즘' 카테고리의 다른 글

Find if Array Can Be Sorted  (0) 2025.02.21
Find Unique Binary String  (0) 2025.02.20
String Compression III  (0) 2025.02.20
Rotate String  (0) 2025.02.20
Delete Characters to Make Fancy String  (0) 2025.02.20
블로그 이미지

짬뽕얼큰하게

,

String Compression III

알고리즘 2025. 2. 20. 08:47

Leetcode Problem:

Summary

  • Given a string word, compress it using the algorithm where a maximum length prefix of a single character c repeating at most 9 times is removed, and the length of the prefix followed by c is appended to the compressed string.

Approach

  • The approach used is to iterate through the input string and whenever a different character is encountered, the length of the previous character's prefix is appended to the compressed string, followed by the character
  • This process continues until the end of the string.

Complexity

  • O(n), where n is the length of the input string, because each character in the string is visited once.

Explanation

  • The code uses a dynamic programming approach to solve the problem
  • It first initializes a counter cnt to keep track of the length of the current character's prefix
  • It then iterates through the input string, and whenever a different character is encountered, it calculates the length of the previous character's prefix (a and b) and appends it to the compressed string
  • The counter cnt is then reset to 0 and the process continues until the end of the string.

Solution Code:


class Solution {
public:
    int str_cnt[256];
    string compressedString(string word) {
        int cnt = 0;
        char beforeChar = 'a'-1;
        string res = "";
        for(char c : word) {
            if(c != beforeChar){
                int a = cnt / 9;
                for(int i = 0 ; i < a; i++){
                    res += "9" + string(1, beforeChar);
                }
                int b = cnt % 9;
                if (b > 0){
                    res += to_string(b) + string(1, beforeChar);
                }
                cnt = 0;
            }
            cnt++;
            beforeChar = c;
        }
        int a = cnt / 9;
        for(int i = 0 ; i < a; i++){
            res += "9" + string(1, beforeChar);
        }
        int b = cnt % 9;
        if (b > 0){
            res += to_string(b) + string(1, beforeChar);
        }
        
        return res;
    }
};

'알고리즘' 카테고리의 다른 글

Find Unique Binary String  (0) 2025.02.20
Minimum Number of Changes to Make Binary String Beautiful  (0) 2025.02.20
Rotate String  (0) 2025.02.20
Delete Characters to Make Fancy String  (0) 2025.02.20
Minimum Total Distance Traveled  (0) 2025.02.20
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

티스토리툴바