짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/05 글 목록 (2 Page)

'2025/05'에 해당되는 글 16건

Build Array from Permutation

알고리즘 2025. 5. 6. 23:14

Leetcode Problem:

Summary

  • Given a zero-based permutation, build an array where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

Approach

  • This solution uses a simple iterative approach where it iterates over the input array and uses the value at each index as the index for the next value in the output array.

Complexity

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

Explanation

  • The solution uses a vector to store the output array and iterates over the input array
  • For each index in the input array, it uses the value at that index as the index for the next value in the output array
  • This approach is simple and efficient, with a time complexity of O(n) where n is the length of the input array.

Solution Code:


class Solution {
public:
    vector ans;
    vector buildArray(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            ans.push_back(nums[nums[i]]);
        }
        return ans;
    }
};

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

Find Minimum Time to Reach Last Room II  (1) 2025.05.08
Find Minimum Time to Reach Last Room I  (0) 2025.05.07
Domino and Tromino Tiling  (1) 2025.05.05
Number of Equivalent Domino Pairs  (0) 2025.05.04
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
블로그 이미지

짬뽕얼큰하게

,

Domino and Tromino Tiling

알고리즘 2025. 5. 5. 11:33

Leetcode Problem:

Summary

  • The problem requires finding the number of ways to tile a 2 x n board with 2 x 1 dominoes and a tromino shape, with the answer being modulo 10^9 + 7.

Approach

  • The solution uses dynamic programming to calculate the number of ways to tile the board
  • It initializes an array `memo` to store the number of ways to tile a board of length `i`, and then iterates from `i = 4` to `n` to calculate the number of ways to tile a board of length `i`
  • For each `i`, it calculates the number of ways to tile a board of length `i` by considering the number of ways to tile a board of length `i-1` and `i-2`, and adds the number of ways to tile a board of length `i-3` to the result, taking into account the modulo operation to avoid overflow.

Complexity

  • O(n)

Explanation

  • The solution uses a dynamic programming approach to calculate the number of ways to tile the board
  • It initializes an array `memo` to store the number of ways to tile a board of length `i`, and then iterates from `i = 4` to `n` to calculate the number of ways to tile a board of length `i`
  • For each `i`, it calculates the number of ways to tile a board of length `i` by considering the number of ways to tile a board of length `i-1` and `i-2`, and adds the number of ways to tile a board of length `i-3` to the result, taking into account the modulo operation to avoid overflow
  • The time complexity of the solution is O(n) because it iterates from `i = 4` to `n` once, and the space complexity is O(n) because it stores the number of ways to tile a board of length `i` in the `memo` array.

Solution Code:


#define MOD 1000000007
class Solution {
public:
    int memo[1001];
    int numTilings(int n) {
        memo[0] = 1;
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 5;
        for(int i = 4; i <= n; i++){
            memo[i] = (memo[i-1] + memo[i-2])%MOD;
            for(int j = i - 3; j >= 0; j--){
                memo[i] += (memo[j]*2)%MOD;
                memo[i] %= MOD;
            }
        }
        return memo[n];
    }
};

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

Find Minimum Time to Reach Last Room I  (0) 2025.05.07
Build Array from Permutation  (2) 2025.05.06
Number of Equivalent Domino Pairs  (0) 2025.05.04
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Push Dominoes  (2) 2025.05.02
블로그 이미지

짬뽕얼큰하게

,

Number of Equivalent Domino Pairs

알고리즘 2025. 5. 4. 09:25

Leetcode Problem:

Summary

  • Given a list of dominoes, find the number of pairs where one domino can be rotated to be equal to another domino.

Approach

  • The approach used is to first count the occurrences of each domino, then calculate the number of pairs by summing up the combinations of each domino, considering that each pair can be represented by two dominoes.

Complexity

  • O(n log n) due to sorting, where n is the number of dominoes, and O(1) for the space complexity where n is the maximum possible value of a domino.

Explanation

  • The solution works by first creating a hashmap to store the occurrences of each domino
  • Then it iterates over the hashmap and calculates the number of pairs for each domino by summing up the combinations of each domino, considering that each pair can be represented by two dominoes
  • The time complexity is O(n log n) due to sorting, and the space complexity is O(1) for the hashmap.

Solution Code:


class Solution {
public:
    unordered_map cnt;
    int numEquivDominoPairs(vector>& dominoes) {
        for(int i = 0 ; i < dominoes.size() ; i++){
            int a = dominoes[i][0];
            int b = dominoes[i][1];
            if(a > b){
                int t = a;
                a = b;
                b = t;
            }
            cnt[a*10 + b]++;
        }
        int ans = 0;
        for(auto iter = cnt.begin(); iter != cnt.end(); iter++){
            ans += (iter->second * (iter->second-1)) / 2;
        }
        return ans;
    }
};

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

Build Array from Permutation  (2) 2025.05.06
Domino and Tromino Tiling  (1) 2025.05.05
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Push Dominoes  (2) 2025.05.02
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
블로그 이미지

짬뽕얼큰하게

,

Minimum Domino Rotations For Equal Row

알고리즘 2025. 5. 3. 21:23

Leetcode Problem:

Summary

  • The problem is to find the minimum number of rotations required to make all values in the tops or bottoms array equal
  • The function takes two arrays, tops and bottoms, as input and returns the minimum number of rotations
  • If it's not possible to make all values equal, the function returns -1.

Approach

  • The solution code uses a two-pass approach
  • First, it checks if it's possible to make all values in the tops or bottoms array equal by checking if there's a common value between the two arrays
  • If it's not possible, the function returns -1
  • Otherwise, it counts the number of rotations required to make all values in the tops or bottoms array equal.

Complexity

  • O(n), where n is the length of the tops and bottoms arrays
  • The function makes two passes through the arrays, one for each possible common value.

Explanation

  • The solution code first checks if it's possible to make all values in the tops or bottoms array equal by checking if there's a common value between the two arrays
  • If it's not possible, the function returns -1
  • Otherwise, it counts the number of rotations required to make all values in the tops or bottoms array equal
  • The function uses two counters, cnt1 and cnt2, to count the number of rotations required to make all values in the tops and bottoms arrays equal, respectively
  • The function returns the minimum of cnt1 and cnt2.

Solution Code:


class Solution {
public:
    int minDominoRotations(vector& tops, vector& bottoms) {
        int cur = tops[0];
        bool success = true;
        for(int i = 0 ; i < tops.size(); i++){
            if(tops[i] == cur || bottoms[i] == cur) continue;
            success = false;
            break;
        }
        if(!success){
            success = true;
            cur = bottoms[0];
            for(int i = 0 ; i < tops.size(); i++){
                if(tops[i] == cur || bottoms[i] == cur) continue;
                success = false;
                break;
            }
        }
        if(!success) return -1;

        int cnt1 = 0;
        int cnt2 = 0;
        for(int i = 0 ; i < tops.size(); i++){
            if(tops[i] != cur) cnt1++;
            if(bottoms[i] != cur) cnt2++;
        }
        return cnt1 < cnt2 ? cnt1 : cnt2;
    }
};

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

Domino and Tromino Tiling  (1) 2025.05.05
Number of Equivalent Domino Pairs  (0) 2025.05.04
Push Dominoes  (2) 2025.05.02
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Find Numbers with Even Number of Digits  (0) 2025.04.30
블로그 이미지

짬뽕얼큰하게

,

Push Dominoes

알고리즘 2025. 5. 2. 19:05

Leetcode Problem:

Summary

  • This problem is about simulating the movement of dominoes in a line
  • The dominoes can be pushed to the left or to the right, and they will move in the opposite direction if pushed from both sides.

Approach

  • The approach used in the solution is to iterate through the dominoes and for each domino, check if it has been pushed to the left or to the right
  • If it has been pushed to the left, all the dominoes to its left that have not been pushed will also be pushed to the left
  • If it has been pushed to the right, all the dominoes to its right that have not been pushed will be pushed to the right
  • If a domino has been pushed from both sides, it will stay still.

Complexity

  • O(n)

Explanation

  • The time complexity of the solution is O(n) because we are iterating through the dominoes once
  • The space complexity is O(1) because we are not using any extra space that scales with the input size.

Solution Code:


class Solution {
public:
    string pushDominoes(string dominoes) {
        for(int i = 0 ; i < dominoes.size(); i++){
            if(dominoes[i] == 'L'){
                int j = i-1;
                while(j >= 0 && dominoes[j] == '.'){
                    dominoes.at(j) = 'L';
                    j--;
                }
            } else if(dominoes[i] == 'R'){
                int j = i+1;
                while(j < dominoes.size() && dominoes[j] == '.'){
                    j++;
                }
                if(j >= dominoes.size() || dominoes[j] == 'R'){
                    for(; i < j; i++){
                        dominoes.at(i) = 'R';
                    }
                    if(j < dominoes.size() && dominoes[j] == 'R'){
                        i--;
                    }
                } else{
                    int k = i + 1;
                    int l = j - 1;
                    while(k < l){
                        dominoes.at(k) = 'R';
                        dominoes.at(l) = 'L';
                        k++;
                        l--;
                    }
                    i = j;
                }
            }
        }
        return dominoes;
    }
};

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

Number of Equivalent Domino Pairs  (0) 2025.05.04
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Find Numbers with Even Number of Digits  (0) 2025.04.30
Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
블로그 이미지

짬뽕얼큰하게

,

Maximum Number of Tasks You Can Assign

알고리즘 2025. 5. 1. 23:09

Leetcode Problem:

Summary

  • The problem requires to find the maximum number of tasks that can be completed with given tasks, workers, pills, and strength
  • Each task has a strength requirement, each worker has a strength, and there are magical pills that can increase a worker's strength.

Approach

  • The solution uses a binary search approach
  • It first sorts the tasks and workers arrays
  • Then, it performs a binary search between the minimum and maximum possible number of tasks that can be completed
  • In each iteration of the binary search, it checks if the current number of tasks can be completed by assigning the workers to the tasks
  • If it can, it moves the left pointer to the current number of tasks
  • Otherwise, it moves the right pointer to the previous number of tasks
  • Finally, it returns the left pointer as the maximum number of tasks that can be completed.

Complexity

  • The time complexity of the solution is O(n log n) due to the sorting of the tasks and workers arrays, where n is the number of tasks or workers
  • The space complexity is O(n) for the sorting of the tasks and workers arrays.

Explanation

  • The solution first sorts the tasks and workers arrays
  • Then, it performs a binary search between the minimum and maximum possible number of tasks that can be completed
  • In each iteration of the binary search, it checks if the current number of tasks can be completed by assigning the workers to the tasks
  • If it can, it moves the left pointer to the current number of tasks
  • Otherwise, it moves the right pointer to the previous number of tasks
  • Finally, it returns the left pointer as the maximum number of tasks that can be completed
  • The solution uses a multiset to keep track of the workers' strength after assigning the magical pills.

Solution Code:


class Solution {
public:
    int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) {
        int left = 0, right = min(tasks.size(), workers.size());

        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        while(left < right) {
            int mid = (left + right + 1) / 2;
            int usedPills = 0;
            multiset workersFree(workers.end() - mid, workers.end());

            bool canAssign = true;
            for(int i = mid - 1; i >= 0; --i) {
                auto it = prev(workersFree.end());

                if(*it < tasks[i]) {
                    it = workersFree.lower_bound(tasks[i] - strength);
                    if(it == workersFree.end()) {
                        canAssign = false;
                        break;
                    }
                    ++usedPills;
                    if(usedPills > pills) {
                        canAssign = false;
                        break;
                    }
                }
                workersFree.erase(it);
            }

            if(canAssign)
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

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

Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Push Dominoes  (2) 2025.05.02
Find Numbers with Even Number of Digits  (0) 2025.04.30
Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
Count Subarrays of Length Three With a Condition  (1) 2025.04.27
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   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

티스토리툴바