'2025/02'에 해당되는 글 176건

Leetcode Problem:

• Sliding Puzzle

Summary

• Find the least number of moves to solve a sliding puzzle

Approach

• Breadth-First Search (BFS) algorithm is used to explore all possible states of the puzzle
• The algorithm starts with the initial state and generates all possible next states by swapping each empty tile with each adjacent tile
• The algorithm continues until it finds the target state or exhausts all possible states.

Complexity

• O(15*6^6) = O(2^8) due to the use of BFS and the size of the search space

Explanation

• The solution code defines a BFS algorithm to solve the sliding puzzle
• It starts with the initial state and generates all possible next states by swapping each empty tile with each adjacent tile
• The algorithm continues until it finds the target state or exhausts all possible states
• The time complexity of the algorithm is O(2^8) due to the use of BFS and the size of the search space.

Solution Code:

struct _node{
    char board[2][3];
    int cnt;
};
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
class Solution {
public:
    bool visited[6][6][6][6][6][6];
    queue<_node> que;
    int slidingPuzzle(vector>& board) {
        _node init;
        for(int i = 0 ; i < 2; i++){
            for(int j = 0; j < 3; j++){
                init.board[i][j] = board[i][j];
            }
        }
        init.cnt = 0;
        que.push(init);
        visited[board[0][0]][board[0][1]][board[0][2]][board[1][0]][board[1][1]][board[1][2]] = true;
        while(!que.empty()){
            _node nod = que.front();
            que.pop();
            if(nod.board[1][2] == 0 && nod.board[0][0] == 1 && 
            nod.board[0][1] == 2 && nod.board[0][2] == 3 &&
            nod.board[1][0] == 4 && nod.board[1][1] == 5){
                return nod.cnt;
            }
            int r=-1, c = -1;
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 3; j++){
                    if(nod.board[i][j] == 0){
                        r = i;
                        c = j;
                        break;
                    }
                }
                if(r != -1) break;
            }

            for(int i = 0 ; i < 4; i++){
                int nr = r + dy[i];
                int nc = c + dx[i];
                if(nr < 0 || nr >= 2 || nc < 0 || nc >= 3){
                    continue;
                }
                _node next = nod;
                next.cnt++;
                char t = next.board[nr][nc];
                next.board[nr][nc] = next.board[r][c];
                next.board[r][c] = t;
                if(visited[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]] ){
                    continue;
                }

                visited[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]] = true;
                que.push(next);
            }

        }
        return -1;
    }
};

Leetcode Problem:

• Maximum Matrix Sum

Summary

• Given an n x n matrix, find the maximum sum of its elements by multiplying adjacent elements by -1.

Approach

• The solution works by first calculating the sum of the absolute values of all elements in the matrix
• Then, it checks if there is an even number of negative elements
• If there is, it subtracts twice the minimum value from the sum
• This operation effectively flips the sign of the negative elements, which can increase the sum.

Complexity

• O(n^2) where n is the size of the matrix

Explanation

• The solution iterates over each element in the matrix once to calculate the sum and count the number of negative elements
• Then, it checks if there is an odd number of negative elements and subtracts twice the minimum value from the sum if necessary
• This approach ensures that the maximum sum is achieved by flipping the sign of the negative elements.

Solution Code:

class Solution {
public:
    long long maxMatrixSum(vector>& matrix) {
        int cnt = 0;
        int minValue = 100001;
        long long sum = 0;
        bool isZero = false;
        for(int i = 0 ; i < matrix.size(); i++){
            for(int j = 0 ; j < matrix[0].size(); j++){
                sum += abs(matrix[i][j]);
                if(matrix[i][j] < 0){
                    cnt++;
                }
                minValue = min(minValue, abs(matrix[i][j]));
                if(matrix[i][j] == 0){
                    isZero = true;
                }
            }
        }
        if(!isZero && (cnt &1)){
            sum -= minValue*2;
        }
        return sum;
    }
};

Leetcode Problem:

• Rotating the Box

Summary

• Given an m x n matrix of characters boxGrid representing a side-view of a box, rotate the box 90 degrees clockwise and return the resulting matrix.

Approach

• The approach used is to first transpose the boxGrid and then reverse each row of the transposed matrix
• This is because the problem requires us to rotate the box 90 degrees clockwise, which can be achieved by first flipping the box horizontally and then flipping it vertically.

Complexity

• O(m*n) where m is the number of rows and n is the number of columns in the boxGrid.

Explanation

• The solution code first creates a new 2D vector rotateBox to store the resulting matrix
• It then iterates over each row in the boxGrid and performs the following operations: 1
• It starts from the rightmost column and moves towards the left
• If the current cell is a stone (#), it moves the stone to the bottom right corner of the row and marks the stone as empty (.) if it's not the last stone in the row
• 2
• If the current cell is an obstacle (*), it moves the obstacle to the left of the stone
• 3
• If the current cell is empty (.), it simply moves to the next cell
• After processing each row, the code transposes the boxGrid and reverses each row to achieve the rotation
• Finally, it returns the resulting matrix.

Solution Code:

class Solution {
public:
    vector> rotateTheBox(vector>& box) {
        vector> rotateBox;
        for(int i = 0 ; i< box.size(); i++){
            int r = box[0].size() - 1;
            int l = r;
            while(l >= 0){
                if(box[i][l] == '#'){
                    box[i][r] = box[i][l];
                    if(l != r){
                        box[i][l] = '.';
                    }
                    r--;
                } else if(box[i][l] == '*'){
                    r = l - 1;
                }
                l--;
            }

        }
        int R = box.size();
        int C = box[0].size();
        for(int j=0; j < C; j++){
            rotateBox.push_back(vector());
            for(int i = 0; i < R; i++){
                rotateBox[j].push_back(box[R-i-1][j]);
            }
        }
        
        


        return rotateBox;
    }
};

Leetcode Problem:

• Flip Columns For Maximum Number of Equal Rows

Summary

• Find the maximum number of rows that have all values equal after some number of flips in a binary matrix.

Approach

• Use a hash map to store the frequency of each string representation of the columns
• Then, for each string, calculate the maximum number of rows that can be made equal by flipping the bits in the column
• The maximum number of rows that can be made equal across all strings is the maximum of these values.

Complexity

• O(m * n * log(n))

Explanation

• The solution works by first creating a hash map where each key is a string representation of a column and the value is the frequency of that column
• Then, for each string, it calculates the maximum number of rows that can be made equal by flipping the bits in the column
• This is done by counting the number of bits that are different between the string and the column
• The maximum number of rows that can be made equal across all strings is the maximum of these values.

Solution Code:

template 
struct _vector{
    T* arr;
    int size;
    int capacity;
    _vector(){
        size = 0;
        capacity = 2;
        arr = new T[capacity];
    }
    void push(T a){
        if(size == capacity){
            capacity *= 2;
            T* tmp = new T[capacity];
            for(int i = 0 ; i < size ; i++){
                tmp[i] = arr[i];
            }
            delete[] arr;
            arr = tmp;
        }
        arr[size++] = a;
    }
    T operator[](int idx){
        return arr[idx];
    }
};

struct _node{
    string s;
    int cnt;
};

struct _node2{
    unsigned int key;
    int idx;
};

#define MAP_SIZE 300
struct _map{
    _vector<_node> arr[MAP_SIZE];
    _vector<_node2> nodeList;
    _map(){
        for(int i = 0 ; i < MAP_SIZE; i++){
            arr[i].size = 0;
        }
        nodeList.size = 0;
    }
    void push(string s){
        unsigned int key = 1;
        for(int i = 0 ; i < s.size(); i++){
            key *= s[i] - 'a';
            key *= 26;
            key %= MAP_SIZE;
        }
        for(int i = 0; i < arr[key].size; i++){
            if(arr[key][i].s.compare(s) == 0){
                arr[key].arr[i].cnt++;
                return;
            }
        }
        arr[key].push({s, 1});
        nodeList.push({key, arr[key].size - 1});
    }
    int size(){
        return nodeList.size;
    }
    _node getItem(_node2 nod){
        return arr[nod.key][nod.idx];
    }
};

class Solution {
public:
    int maxEqualRowsAfterFlips(vector>& matrix) {
        _map hmap;
        for(int i = 0 ; i < matrix.size(); i++){
            string s = "";
            int first = matrix[i][0];
            for(int j = 0 ; j < matrix[i].size(); j++){
                if(first == matrix[i][j]){
                    s += "1";
                } else {
                    s += "0";
                }
            }
            hmap.push(s);
        }
        int ans = 0;
        for(int i = 0; i < hmap.size(); i++){
            ans = max(ans, hmap.getItem(hmap.nodeList[i]).cnt);
        }
        return ans;
    }
};

Leetcode Problem:

• Count Unguarded Cells in the Grid

Summary

• This solution calculates the number of unguarded cells in a grid given the positions of guards and walls.

Approach

• The approach used is to first create a map of the grid where each cell is initially unguarded (0)
• Then, we mark the positions of the walls and guards on the map
• After that, we perform a depth-first search (DFS) from each guard position to mark the cells that can be seen by the guard
• Finally, we count the number of unguarded cells by iterating over the map.

Complexity

• O(m*n + m*n*4) = O(m*n) because the DFS operations are bounded by the number of cells in the grid.

Explanation

• The provided C++ code initializes a 2D map of size m x n with all cells unguarded
• It then marks the positions of the walls and guards on the map
• After that, it performs a depth-first search (DFS) from each guard position to mark the cells that can be seen by the guard
• The DFS function recursively explores the neighboring cells in four directions (north, east, south, and west) and marks them as guarded if they are not already marked as walls or other guards
• Finally, it counts the number of unguarded cells by iterating over the map and returns the result.

Solution Code:

int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
class Solution {
public:
    vector< vector> map;
    void fill(int m, int n, int r, int c, int dir, int v){
        if(r < 0 || r >= m || c < 0 || c >= n || map[r][c] == 2 || map[r][c] == v){
            return;
        }
        map[r][c] = v; 
        fill(m, n, r + dy[dir], c + dx[dir], dir, v);
    }
    int countUnguarded(int m, int n, vector>& guards, vector>& walls) {
        for(int i = 0 ; i < m; i++){
            map.push_back(vector());
            for(int j = 0; j < n; j++){
                map[i].push_back(0);
            }
        }
        for(int i = 0; i < walls.size(); i++){
            int r = walls[i][0];
            int c = walls[i][1];
            map[r][c] = 2;
        }
        for(int i = 0 ; i < guards.size(); i++){
            int r = guards[i][0];
            int c = guards[i][1];
            for(int j = 0 ; j < 4; j++){
                fill(m, n, r + dy[j], c + dx[j], j, j < 2 ? 4 : 5);
            }
            map[r][c] = 1;
        }
        int ans = 0;
        for(int i = 0 ; i < m; i++){
            for(int j = 0 ; j < n; j++){
                if(map[i][j] == 0){
                    ans++;
                }
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Take K of Each Character From Left and Right

Summary

• Given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k, find the minimum number of minutes needed to take at least k of each character.

Approach

• The approach used is to use a sliding window technique
• The window is initially set to the entire string
• If the count of each character in the window is greater than or equal to k, the window is moved to the right
• If the count of each character in the window is less than k, the window is moved to the left
• The minimum number of minutes is updated whenever a valid window is found.

Complexity

• O(N^2) where N is the length of the string

Explanation

• The solution first initializes a count array to keep track of the count of each character in the string
• It then iterates over the string and checks if the count of each character is greater than or equal to k
• If it is, the window is moved to the right
• If it is not, the window is moved to the left
• The minimum number of minutes is updated whenever a valid window is found
• The solution then returns the minimum number of minutes.

Solution Code:

class Solution {
public:
    int cnt[256];
    int takeCharacters(string s, int k) {
        int N = s.size();
        int ans= -1;
        int i;
        for(i = 0 ; i < N; i++){
            cnt[s[i]]++;
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = i+1;
                break;
            }
        }
        if(ans == -1) return -1;
        int r = N -1;
        while(i>=0){
            cnt[s[i]]--;
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = min(ans,i + N - r - 1);
                i--;
                continue;
            }
            while (r >= 0 && (cnt['a'] < k || cnt['b'] < k || cnt['c'] < k)){
                cnt[s[r]]++;
                r--;
            }
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = min(ans, i + 1 + N - r -1);
            }

            i--;
        }
        
        return ans;
    }
};

Leetcode Problem:

• Maximum Sum of Distinct Subarrays With Length K

Summary

• Find the maximum subarray sum of all the subarrays of a given array that meet the conditions of having a length of k and all elements distinct.

Approach

• Use a sliding window approach with a hashmap to store the previous index of each number
• Iterate through the array, adding each number to the current sum and removing the number at the leftmost index of the window if it's out of the window
• If the window size is equal to k, update the maximum sum if the current sum is greater.

Complexity

• O(n * k) where n is the length of the array, because in the worst case we might have to check all numbers for each window size k.

Explanation

• The solution uses a sliding window approach with a hashmap to store the previous index of each number
• We initialize the hashmap and the maximum sum
• Then we iterate through the array, adding each number to the current sum and removing the number at the leftmost index of the window if it's out of the window
• If the window size is equal to k, we update the maximum sum if the current sum is greater
• We use a hashmap to store the previous index of each number to efficiently check if a number has been seen before in the current window.

Solution Code:

class Solution {
public:
    long long maximumSubarraySum(vector& nums, int k) {
        long long res = 0;
        unordered_map prev_idx;  // num -> prev index of num
        long long cur_sum = 0;
        
        int l = 0;
        
        for (int r = 0; r < nums.size(); r++) {
            cur_sum += nums[r];
            
            int i = -1;
            if (prev_idx.find(nums[r]) != prev_idx.end()) {
                i = prev_idx[nums[r]];
            }
            
            while (l <= i || r - l + 1 > k) {
                cur_sum -= nums[l];
                l++;
            }
            
            if (r - l + 1 == k) {
                res = max(res, cur_sum);
            }
            
            prev_idx[nums[r]] = r;
        }
        
        return res;
    }
};

Leetcode Problem:

• Defuse the Bomb

Summary

• A circular array code of length n and a key k are given
• The goal is to decrypt the code by replacing every number with the sum of the next k numbers if k is positive, the sum of the previous k numbers if k is negative, and 0 if k is 0.

Approach

• The approach used is to iterate through the array and for each element, calculate the sum of the next k numbers if k is positive, the sum of the previous k numbers if k is negative, and 0 if k is 0
• The sum is then appended to the result vector.

Complexity

• O(n * |k|) where n is the length of the code array and |k| is the absolute value of the key k.

Solution Code:

class Solution {
public:
    vector decrypt(vector& code, int k) {
        vector ans;
        int N = code.size();
        for(int i = 0 ; i < N; i++){
            int sum = 0;
            for(int j = 1; j <= abs(k); j++){
                int idx;
                if (k > 0){
                    idx = (i + j) % N;
                } else if(k < 0) {
                    idx = (i - j + N) % N;
                } else{
                    break;
                }
                sum += code[idx];
            }
            ans.push_back(sum);
        }
        return ans;
    }
};

Leetcode Problem:

• Shortest Subarray with Sum at Least K

Summary

• Given an integer array and an integer k, return the length of the shortest non-empty subarray with a sum of at least k.

Approach

• Use a deque to store the prefix sum and its corresponding end index
• Iterate through the array, updating the prefix sum and checking if it's greater than or equal to k
• If it is, update the result with the minimum length
• If the prefix sum minus the front element is greater than or equal to k, remove the front element from the deque
• If the back element's prefix sum is greater than the current prefix sum, remove it from the deque
• Finally, return the result or -1 if no such subarray exists.

Complexity

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

Explanation

• The time complexity is O(n) because we're doing a single pass through the array
• The space complexity is O(n) for storing the deque.

Solution Code:

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        int res = INT_MAX;
        long long curSum = 0;
        deque> q; // (prefix_sum, end_idx)
        for(int r = 0; r < nums.size(); r++){
            curSum += nums[r];

            if(curSum >= k){
                res = min(res, r + 1);
            }

            while (!q.empty() && curSum - q.front().first >= k){
                auto [prefix, endIdx] = q.front();
                q.pop_front();
                res = min(res, r - endIdx);
            }
            while (!q.empty() && q.back().first > curSum) {
                q.pop_back();
            }
            q.push_back({curSum, r});
        }
        
        return res == INT_MAX ? -1 : res;
    }
};

Leetcode Problem:

• Find the Power of K-Size Subarrays I

Summary

• This solution is used to find the power of all subarrays of size k in a given array of integers
• The power of a subarray is defined as its maximum element if all its elements are consecutive and sorted in ascending order, otherwise -1.

Approach

• This solution uses a sliding window approach with two nested loops to check for consecutive elements
• It keeps track of the current window's start index, end index, and the count of consecutive elements
• If the count of consecutive elements equals k, the maximum element in the current window is added to the result array
• Otherwise, -1 is added.

Complexity

• O(n*k) where n is the size of the input array, k is the size of the subarray

Solution Code:

class Solution {
public:
    vector resultsArray(vector& nums, int k) {
        vector ans;
        int acd_cnt = 1;
        int cmp_num = nums[0];
        for(int i = 1 ; i < k ;i++){
            if(cmp_num + 1 == nums[i]){
                acd_cnt++;
            } else {
                acd_cnt = 1;
            }
            cmp_num = nums[i];
        }
        if(acd_cnt == k){
            ans.push_back(cmp_num);
        } else {
            ans.push_back(-1);
        }
        for(int i = k ; i < nums.size(); i++){
            if(cmp_num + 1 == nums[i]){
                acd_cnt++;
            } else {
                acd_cnt = 1;
            }
            if(acd_cnt >= k){
                ans.push_back(nums[i]);
            } else {
                ans.push_back(-1);
            }
            cmp_num = nums[i];
        }
        return ans;
    }
};