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

Remove All Occurrences of a Substring

알고리즘 2025. 2. 11. 23:11

Leetcode Problem:

Summary

  • Given a string s and a substring part, remove all occurrences of part from s

Approach

  • Use a stack data structure to keep track of the characters in s and check for occurrences of part
  • If part is found, remove it from the stack by popping the characters one by one.

Complexity

  • O(n*m) where n is the length of s and m is the length of part

Explain

  • The solution iterates over the string s and checks for occurrences of part by comparing the characters at the end of part with the characters in the stack
  • If part is found, it removes it from the stack by popping the characters one by one
  • The time complexity is O(n*m) because in the worst case, the stack size can be n and the number of occurrences of part can be m.

Solution Code:


class Solution {
public:
    vector st;
    string removeOccurrences(string s, string part) {
        for(int i = 0 ; i < s.size(); i++){
            st.push_back(s[i]);
            if(st.size() >= part.size()){
                bool success = true;
                for(int j = 0; j < part.size(); j++){
                    if(st[st.size()-j -1] != part[part.size() - j - 1]){
                        success = false;
                        break;
                    }
                }
                if(success){
                    for(int j = 0 ; j < part.size(); j++){
                        st.pop_back();
                    }
                }
            }
        }
        string ans = "";
        for(int i = 0 ; i < st.size(); i++){
            ans += st[i];
        }
        return ans;
    }
};

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

Spiral Matrix IV  (0) 2025.02.12
Linked List in Binary Tree  (0) 2025.02.12
Delete Nodes From Linked List Present in Array  (0) 2025.02.11
Find Missing Observations  (0) 2025.02.11
Walking Robot Simulation  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Delete Nodes From Linked List Present in Array

알고리즘 2025. 2. 11. 09:09

Leetcode Problem:

Summary

  • Given an array of integers and the head of a linked list, return the head of the modified linked list after removing nodes with values that exist in the array.

Approach

  • Use a set to store the values in the array, then traverse the linked list and create a new linked list with only the nodes that have values not in the set.

Complexity

  • O(n + m) where n is the number of nodes in the linked list and m is the number of elements in the array

Explain

  • The solution works by first creating a set of the values in the array
  • Then it traverses the linked list, checking if each node's value is in the set
  • If it is, the node is skipped
  • If not, a new node is created with the same value and it becomes the head of the modified linked list
  • This process continues until all nodes have been traversed.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    set s;
    ListNode* ans;
    void traversal(ListNode* head){
        if (head == nullptr) return;
        traversal(head->next);
        if( s.find(head->val) != s.end()) return;

        ListNode* temp = new ListNode(head->val, ans);
        ans = temp;
    }
    ListNode* modifiedList(vector& nums, ListNode* head) {
        for(int i = 0 ; i < nums.size(); i++){
            s.insert(nums[i]);
        }
        traversal(head);
        return ans;    
    }
};

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

Linked List in Binary Tree  (0) 2025.02.12
Remove All Occurrences of a Substring  (0) 2025.02.11
Find Missing Observations  (0) 2025.02.11
Walking Robot Simulation  (0) 2025.02.11
Sum of Digits of String After Convert  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Find Missing Observations

알고리즘 2025. 2. 11. 09:06

Leetcode Problem:

Summary

  • Find the missing 6-sided dice rolls to achieve a given average value.

Approach

  • This solution calculates the total sum of all rolls by multiplying the mean by the total number of rolls
  • It then subtracts the sum of the known rolls from the total sum to find the sum of the missing rolls
  • The solution then iterates through the missing rolls, assigning the average value to each roll and adjusting the value if necessary to ensure the total sum is divisible by the total number of rolls.

Complexity

  • O(n)

Explain

  • The time complexity of this solution is O(n) because it iterates through the missing rolls once
  • The space complexity is O(n) because it stores the missing rolls in a vector.

Solution Code:


class Solution {
public:
    vector missingRolls(vector& rolls, int mean, int n) {
        vector ans;
        int m = rolls.size();
        int totalSum = (m + n) * mean;
        for(int i = 0 ; i < m; i++){
            totalSum -= rolls[i];
        }
        if(totalSum < n || totalSum > n*6) return ans;
        for(int i = 0 ; i < n; i++){
            ans.push_back(totalSum/n);
            if (totalSum % n != 0){
                ans[i] += 1;
                totalSum--;
            }
        }
        return ans;
    }
};

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

Remove All Occurrences of a Substring  (0) 2025.02.11
Delete Nodes From Linked List Present in Array  (0) 2025.02.11
Walking Robot Simulation  (0) 2025.02.11
Sum of Digits of String After Convert  (0) 2025.02.11
Find the Student that Will Replace the Chalk  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Walking Robot Simulation

알고리즘 2025. 2. 11. 09:03

Leetcode Problem:

Summary

  • Find the maximum squared Euclidean distance that a robot can reach in a grid while avoiding obstacles.

Approach

  • This solution uses a set to store the positions of obstacles and a loop to iterate through the robot's commands
  • It also uses arrays to represent the possible directions (north, east, south, west) and the current position of the robot
  • The solution updates the current position of the robot and calculates the maximum squared Euclidean distance at each step.

Complexity

  • O(n), where n is the number of commands.

Explain

  • The solution starts by initializing a set to store the positions of obstacles and a variable to store the maximum squared Euclidean distance
  • It then iterates through the robot's commands, updating the current position of the robot and calculating the maximum squared Euclidean distance at each step
  • If the robot encounters an obstacle, it skips the current command and continues to the next one
  • The solution returns the maximum squared Euclidean distance reached by the robot.

Solution Code:


class Solution {
public:
    set> s;
    int robotSim(vector& commands, vector>& obstacles) {
        int ans = 0;
        for(int i = 0 ; i < obstacles.size(); i++){
            int x = obstacles[i][0];
            int y = obstacles[i][1];
            s.insert({y, x});
        }
        int dir = 0;
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        int y = 0;
        int x = 0;
        for(int i = 0 ; i < commands.size(); i++){
            if(commands[i] == -1){
                dir = (dir + 1) %4;
                continue;
            } else if(commands[i] == -2){
                dir = (dir + 3) %4;
                continue;
            } 
            for(int j = 0 ; j < commands[i]; j++){
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny < -30000 || ny > 30000 || nx < -30000 || nx > 30000) continue;
                if (s.find({ny, nx}) != s.end()){
                    continue;
                }

                y = ny;
                x = nx;
                ans = max(ans, (y*y) + (x * x));
            }
        }
        return ans;
        
    }
};

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

Delete Nodes From Linked List Present in Array  (0) 2025.02.11
Find Missing Observations  (0) 2025.02.11
Sum of Digits of String After Convert  (0) 2025.02.11
Find the Student that Will Replace the Chalk  (0) 2025.02.11
Convert 1D Array Into 2D Array  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Sum of Digits of String After Convert

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

Leetcode Problem:

Summary

  • This problem involves converting a string into an integer by replacing each letter with its position in the alphabet, then transforming the integer by summing its digits repeatedly k times.

Approach

  • The approach used is to first convert the string into an integer by subtracting the ASCII value of 'a' from each character and adding 1
  • Then, the integer is transformed by summing its digits using a helper function
  • This process is repeated k times.

Complexity

  • O(n*k) where n is the length of the string and k is the number of transformations.

Explain

  • The solution code defines a class Solution with two methods: getSum and getLucky
  • The getSum method takes a string as input and returns the sum of its digits
  • The getLucky method takes a string and an integer as input and returns the resulting integer after performing the transformations
  • The getLucky method first converts the string into an integer, then repeatedly transforms the integer by summing its digits using the getSum method
  • The process is repeated k times, and the final result is returned.

Solution Code:


class Solution {
public:
    int getSum(string s){
        int sum = 0;
        for(int i = 0 ; i < s.size(); i++){
            sum += s[i] - '0';
        }
        return sum;
    }
    int getLucky(string s, int k) {
        string num = "";
        for(int i = 0 ; i < s.size(); i++){
            num += to_string(s[i] - 'a' + 1);
        }
        int transform;
        while(k--){
            transform = getSum(num);
            num = to_string(transform);
        }
        
        return transform;
    }
};

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

Find Missing Observations  (0) 2025.02.11
Walking Robot Simulation  (0) 2025.02.11
Find the Student that Will Replace the Chalk  (0) 2025.02.11
Convert 1D Array Into 2D Array  (0) 2025.02.11
Path with Maximum Probability  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Find the Student that Will Replace the Chalk

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

Leetcode Problem:

Summary

  • Find the index of the student who will replace the chalk pieces

Approach

  • The solution uses the modulo operator to find the remaining chalk pieces after each student's turn
  • It then iterates through the chalk array to find the student who will run out of chalk first.

Complexity

  • O(n) where n is the number of students

Explain

  • The solution works by first calculating the total amount of chalk available
  • It then uses the modulo operator to find the remaining chalk pieces after each student's turn
  • The student who will run out of chalk first is the one whose index is returned
  • This approach ensures that the student who will replace the chalk is found efficiently, even for large inputs.

Solution Code:


class Solution {
public:
    int chalkReplacer(vector& chalk, int k) {
        long long sum = 0;
        for(int i = 0 ; i < chalk.size(); i++){
            sum += chalk[i];
        }
        k = k % sum;
        for(int i = 0 ; i < chalk.size(); i++){
            k -= chalk[i];
            if (k < 0) return i;
        }
        return 0;
    }
};

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

Walking Robot Simulation  (0) 2025.02.11
Sum of Digits of String After Convert  (0) 2025.02.11
Convert 1D Array Into 2D Array  (0) 2025.02.11
Path with Maximum Probability  (0) 2025.02.11
Most Stones Removed with Same Row or Column  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Convert 1D Array Into 2D Array

알고리즘 2025. 2. 11. 08:53

Leetcode Problem:

Summary

  • Construct a 2D array from a 1D array based on given row and column counts.

Approach

  • The approach used is to create a 2D array and then fill it with elements from the 1D array based on the given row and column counts.

Complexity

  • O(m*n)

Explain

  • The solution code first checks if the total number of elements in the 1D array matches the product of the row and column counts
  • If not, it returns an empty 2D array
  • Otherwise, it creates a 2D array with the given row count and then fills it with elements from the 1D array based on the given column count
  • The outer loop iterates over each row, and the inner loop iterates over each column, assigning the corresponding element from the 1D array to the 2D array.

Solution Code:


class Solution {
public:
    vector> construct2DArray(vector& original, int m, int n) {
        vector> ans;
        if (m*n != original.size()) return {};
        for(int i = 0 ; i < m; i++){
            ans.push_back(vector ());
            for(int j = 0 ; j < n; j++){
                ans[i].push_back(original[n*i + j]);
            }
        }
        return ans;
    }
};

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

Sum of Digits of String After Convert  (0) 2025.02.11
Find the Student that Will Replace the Chalk  (0) 2025.02.11
Path with Maximum Probability  (0) 2025.02.11
Most Stones Removed with Same Row or Column  (0) 2025.02.11
Count Sub Islands  (0) 2025.02.11
블로그 이미지

짬뽕얼큰하게

,

Path with Maximum Probability

알고리즘 2025. 2. 11. 08:49

Leetcode Problem:

Summary

  • Find the path with the maximum probability of success to go from start to end in an undirected weighted graph.

Approach

  • This solution uses a breadth-first search (BFS) approach with a priority queue
  • It starts from the start node and explores all its neighbors
  • For each neighbor, it calculates the maximum probability of success and updates the visited array
  • The process continues until the end node is reached or all nodes are visited.

Complexity

  • O(n + m * log n) where n is the number of nodes and m is the number of edges

Explain

  • The code defines a graph using an adjacency list representation
  • It initializes a visited array to keep track of visited nodes and a queue to store nodes to be visited
  • The main function takes the number of nodes, edges, and probabilities as input and returns the maximum probability of success
  • It uses a BFS approach to explore all nodes and calculates the maximum probability of success for each node
  • The time complexity is O(n + m * log n) due to the priority queue operations.

Solution Code:


struct Node{
    int nod;
    double prob;
};
struct QNode{
    int nod;
    double probSum;
};
class Solution {
public:
    vector v[10001];
    double visited[10001] = {0};
    queue q;
    double maxProbability(int n, vector>& edges, vector& succProb, int start_node, int end_node) {
        double ans = 0;
        for(int i = 0 ; i < edges.size();i++){
            double prob = succProb[i];
            int a = edges[i][0];
            int b = edges[i][1];
            v[a].push_back({b, prob});
            v[b].push_back({a, prob});
        }
        visited[start_node] = 1;
        q.push({start_node, 1});
        while(!q.empty()){
            QNode nod = q.front();
            q.pop();
            if (nod.nod == end_node){
                if(ans < nod.probSum){
                    ans = nod.probSum;
                }
            }
            for(int i = 0 ; i < v[nod.nod].size(); i++){
                Node nextNod = v[nod.nod][i];
                if(nextNod.nod != end_node && visited[nextNod.nod] >= nod.probSum * nextNod.prob){
                    continue;
                }
                if (visited[nextNod.nod] < nod.probSum * nextNod.prob){
                    visited[nextNod.nod] = nod.probSum * nextNod.prob;
                }
                q.push({nextNod.nod, nod.probSum * nextNod.prob});
            }
        }
        
        return ans;

    }
};

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

Find the Student that Will Replace the Chalk  (0) 2025.02.11
Convert 1D Array Into 2D Array  (0) 2025.02.11
Most Stones Removed with Same Row or Column  (0) 2025.02.11
Count Sub Islands  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Most Stones Removed with Same Row or Column

알고리즘 2025. 2. 11. 08:41

Leetcode Problem:

Summary

  • Given a 2D plane with n stones, remove the maximum number of stones that can be removed if a stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Approach

  • Use a union-find data structure to group stones that share the same row or column
  • Then, count the number of connected components to determine the maximum number of stones that can be removed.

Complexity

  • O(n + m) where n is the number of stones and m is the maximum column or row value

Explain

  • Create two maps to store the columns and rows of each stone
  • Then, iterate over each stone and add its column and row to the corresponding maps
  • After that, create a visited array to keep track of the stones that have been visited
  • Then, iterate over each stone and use a helper function to mark all the stones in the same row or column as visited
  • Finally, count the number of connected components in the visited array to determine the maximum number of stones that can be removed.

Solution Code:


class Solution {
public:
    vector cols[10000];
    vector rows[10000];
    bool visited[1000];
    map getIdx;
    void fill(int r, int c){
        int idx = getIdx[r*10000+c];
        if (visited[idx]) return;
        visited[idx] = true;
        for(int i = 0 ; i < cols[r].size(); i++){
            fill(r, cols[r][i]);
        }
        for(int i = 0 ; i < rows[c].size(); i++){
            fill(rows[c][i], c);
        }
    }
    int removeStones(vector>& stones) {
        for(int i = 0 ; i < stones.size(); i++){
            int r = stones[i][0];
            int c = stones[i][1];
            cols[r].push_back(c);
            rows[c].push_back(r);
            getIdx[r*10000+c] = i;
        }
        int uni = 0;
        for(int i = 0 ; i < stones.size(); i++){
            if(visited[i]) continue;
            uni++;
            fill(stones[i][0], stones[i][1]);
        }
        return stones.size() - uni;
    }
};

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

Convert 1D Array Into 2D Array  (0) 2025.02.11
Path with Maximum Probability  (0) 2025.02.11
Count Sub Islands  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
N-ary Tree Postorder Traversal  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Count Sub Islands

알고리즘 2025. 2. 11. 08:38

Leetcode Problem:

Summary

  • Given two binary matrices grid1 and grid2, find the number of islands in grid2 that are sub-islands of islands in grid1.

Approach

  • The approach used is to first fill the grid1 with a unique number representing each island
  • Then, for each cell in grid2, check if it is part of an island in grid1 and if it is a sub-island by recursively checking all its neighboring cells.

Complexity

  • O(m*n*log(m*n)) where m and n are the dimensions of the grid, due to the recursive DFS in the checkSubIsland function.

Explain

  • The solution uses a depth-first search (DFS) approach to fill the grid1 with a unique number representing each island
  • Then, for each cell in grid2, it checks if the cell is part of an island in grid1 by looking up the visited1 grid
  • If the cell is part of an island, it then checks if the cell is a sub-island by recursively calling the checkSubIsland function on all its neighboring cells
  • The count of sub-islands is then incremented and returned as the result.

Solution Code:


class Solution {
public:
    int visited1[501][501];
    int visited2[501][501];
    bool GRID1[501][501];
    bool GRID2[501][501];
    int R, C;
    void fill(int r, int c, int v){
        if (r < 0 || r >= R || c < 0 || c >= C || visited1[r][c] || GRID1[r][c] == 0) return;
        visited1[r][c] = v;
        fill(r + 1, c, v);
        fill(r - 1, c, v);
        fill(r, c + 1, v);
        fill(r, c - 1, v);
    }
    bool checkSubIsland(int r, int c, int v){
        if (r < 0 || r >= R || c < 0 || c >= C || visited2[r][c] || GRID2[r][c] == 0) return true;
        if (visited1[r][c] != v) return false;
        visited2[r][c] = true;
        bool ret = true;
        if (!checkSubIsland(r + 1, c, v)){
            ret = false;
        }
        if (!checkSubIsland(r - 1, c, v)){
            ret = false;
        }
        if (!checkSubIsland(r, c + 1, v)){
            ret = false;
        }
        if (!checkSubIsland(r, c - 1, v)){
            ret = false;
        }

        return ret;
    }
    int countSubIslands(vector>& grid1, vector>& grid2) {
        R = grid1.size();
        C = grid1[0].size();
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                GRID1[i][j] = grid1[i][j];
                GRID2[i][j] = grid2[i][j];
            }
        }
        int cnt = 1;
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(GRID1[i][j] && !visited1[i][j]){
                    fill(i, j, cnt);
                    cnt++;
                }
            }
        }


        int ans = 0;
        for(int i = 0; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(GRID2[i][j] && visited1[i][j] && !visited2[i][j]){
                    if(checkSubIsland(i, j, visited1[i][j])){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

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

Path with Maximum Probability  (0) 2025.02.11
Most Stones Removed with Same Row or Column  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
N-ary Tree Postorder Traversal  (0) 2025.02.10
Binary Tree Postorder Traversal  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   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

티스토리툴바