짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/02/07 글 목록

'2025/02/07'에 해당되는 글 2건

Find the Number of Distinct Colors Among the Balls

알고리즘 2025. 2. 7. 23:35

Leetcode Problem:

Summary

  • Given a limit and a 2D array of queries, find the number of distinct colors among the balls after each query.

Approach

  • The solution uses two unordered maps to keep track of the color count and the current color of each ball
  • It iterates over the queries, updating the color count and current color of each ball, and pushes the number of distinct colors to the result vector.

Complexity

  • O(n), where n is the number of queries

Explain

  • The solution starts by initializing two unordered maps, colorCnt to store the count of each color and curColor to store the current color of each ball
  • It also initializes a variable colornum to store the number of distinct colors
  • Then, it iterates over the queries, updating the color count and current color of each ball
  • If the current color of a ball is the same as its query color, it pushes the current number of distinct colors to the result vector and continues to the next query
  • If the current color of a ball is not the same as its query color, it decrements the count of the current color and increments the count of the query color
  • Finally, it pushes the updated number of distinct colors to the result vector.

Solution Code:


class Solution {
public:
    vector queryResults(int limit, vector>& queries) {
        unordered_map colorCnt;
        unordered_map curColor;
        vector ans;
        int colornum = 0;
        for(int i = 0 ; i < queries.size(); i++){
            int idx = queries[i][0];
            int color = queries[i][1];
            if(curColor[idx] == color){
                ans.push_back(colornum);
                continue;
            }
            if (colorCnt[curColor[idx]] > 0){
                colorCnt[curColor[idx]]--;
                if(colorCnt[curColor[idx]] == 0){
                    colornum--;
                }
            }
            if(colorCnt[color] == 0){
                colornum++;
            }
            curColor[idx] = color;
            colorCnt[color]++;
             
            ans.push_back(colornum);
        }
        return ans;
    }
};

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

Minimum Number of Days to Disconnect Island  (0) 2025.02.09
Regions Cut By Slashes  (0) 2025.02.09
Tuple with Same Product  (0) 2025.02.07
Check if One String Swap Can Make Strings Equal  (0) 2025.02.05
Magic Squares In Grid  (1) 2025.02.05
블로그 이미지

짬뽕얼큰하게

,

Tuple with Same Product

알고리즘 2025. 2. 7. 00:14

Leetcode Problem:

Summary

  • Given an array of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of the array and a!= b!= c!= d.

Approach

  • The approach used is to first filter out duplicate numbers from the input array
  • Then, for each pair of numbers in the filtered array, calculate their product and store them in a vector
  • Finally, count the number of tuples that have the same product by iterating over the vector and using a variable to keep track of the current product and the count of tuples with the same product.

Complexity

  • O(n^2 log n) where n is the length of the input array

Explain

  • The code first initializes a boolean array to keep track of duplicate numbers
  • It then iterates over the input array and pushes each number into the boolean array if it's not already present
  • This step is necessary to filter out duplicate numbers
  • After that, the code sorts the filtered array and iterates over it to calculate the products of each pair of numbers
  • The products are stored in a vector
  • Finally, the code counts the number of tuples that have the same product by iterating over the vector and using a variable to keep track of the current product and the count of tuples with the same product
  • The time complexity of this approach is O(n^2 log n) due to the sorting step.

Solution Code:


class Solution {
public:
    bool num[10001];
    int tupleSameProduct(vector& nums) {
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            if(num[nums[i]]){
                continue;
            }
            nums2.push_back(nums[i]);
            num[nums[i]] = true;
        }
        sort(nums2.begin(), nums2.end());
        vector nums3;
        for(int i = 0 ; i < nums2.size(); i++){
            for(int j = i+1 ; j < nums2.size(); j++){
                nums3.push_back(nums2[i] * nums2[j]);
            }
        }
        int ans = 0;
        sort(nums3.begin(), nums3.end());
        int cnt = 1;
        int cur = nums3[0];
        for(int i = 1 ; i < nums3.size();i++){
            cout << nums3[i] << endl;
            if(cur != nums3[i]){
                if(cnt >= 2){
                    ans += (cnt * (cnt - 1))/2 * 8;
                }
                cnt = 0;
            }
            cnt++;
            cur = nums3[i];
        }
        if(cnt >= 2){
            ans += (cnt * (cnt - 1))/2 * 8;
        }
        return ans;
    }
};

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

Regions Cut By Slashes  (0) 2025.02.09
Find the Number of Distinct Colors Among the Balls  (0) 2025.02.07
Check if One String Swap Can Make Strings Equal  (0) 2025.02.05
Magic Squares In Grid  (1) 2025.02.05
Spiral Matrix III  (0) 2025.02.05
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/02   »
일 월 화 수 목 금 토
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

티스토리툴바