짬뽕얼큰하게의 맨땅에 헤딩 :: 'LeetCode' 태그의 글 목록 (25 Page)

Integer to English Words

알고리즘 2025. 2. 5. 08:43

Leetcode Problem:

Summary

  • Convert a non-negative integer to its English words representation.

Approach

  • The approach used is to recursively break down the number into smaller parts (thousands, millions, billions) and then convert each part to words using a combination of arrays and helper functions.

Complexity

  • O(log n) where n is the number of digits in the input number

Explain

  • The solution code uses three arrays to store the words for thousands, millions, and billions
  • It also uses a helper function `getUnderHndred` to convert numbers less than 100 to words
  • The `numberToWords` function recursively breaks down the input number into smaller parts and then combines the words for each part to form the final result.

Solution Code:


class Solution {
public:
    string digitOf1000[5] = {
        "",
        " Thousand",
        " Million",
        " Billion"

    };
    string digitOf10[11] = {
        "",
        " Ten",
        " Twenty",
        " Thirty",
        " Forty",
        " Fifty",
        " Sixty",
        " Seventy",
        " Eighty",
        " Ninety"
    };
    string underTwenty[21] = {
        "",
        " One",
        " Two",
        " Three",
        " Four",
        " Five",
        " Six",
        " Seven",
        " Eight",
        " Nine",
        " Ten",
        " Eleven",
        " Twelve",
        " Thirteen",
        " Fourteen",
        " Fifteen",
        " Sixteen",
        " Seventeen",
        " Eighteen",
        " Nineteen"
    };
    string getUnderHndred(int num){
        if (num < 20){
            return underTwenty[num];
        }
        string s = "";
        if (num / 10 > 0){
            s += digitOf10[num/10];
        }
        if (num %10 > 0){
            s += underTwenty[num % 10];
        }
        return s;
    }

    string numberToWords(int num) {
        string res = "";
        int cnt = 0;
        if (num == 0) return "Zero";
        while(num){
            string s = "";
            int num2 = (num % 1000);
            if ( num2 / 100){
                s += underTwenty[num2/100] + " Hundred";
            }
            s += getUnderHndred(num2 % 100);
            if (s.compare("") != 0)
                res = s + digitOf1000[cnt] + res;
            num /= 1000;
            cnt++;
        }
        return res.substr(1);
    }
};

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

Magic Squares In Grid  (1) 2025.02.05
Spiral Matrix III  (0) 2025.02.05
Minimum Number of Pushes to Type Word II  (0) 2025.02.05
Kth Distinct String in an Array  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Pushes to Type Word II

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

Leetcode Problem:

Summary

  • Given a string of lowercase English letters, find the minimum number of times the keys will be pushed to type the string after remapping the keys on a telephone keypad.

Approach

  • The approach used is to first count the frequency of each letter in the string, then sort the letters based on their frequency and map them to the keys in a way that minimizes the number of pushes required.

Complexity

  • O(n log n) where n is the number of unique letters in the string

Explain

  • The code first counts the frequency of each letter in the string using an array `word_cnt`
  • Then it sorts the letters based on their frequency using a merge sort algorithm
  • After sorting, it maps the letters to the keys in a way that minimizes the number of pushes required
  • The `merge` function is used to merge two sorted subarrays into a single sorted subarray
  • The `merge_sort` function is used to recursively sort the letters
  • The `minimumPushes` function is the main function that calculates the minimum number of pushes required.

Solution Code:


class Solution {
public:
    int word_cnt[26];
    int sortedAlphabet[26];
    int tmp[26];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while(i <= mid && j <= r){
            if(word_cnt[sortedAlphabet[i]] > word_cnt[sortedAlphabet[j]]){
                tmp[cur++] = sortedAlphabet[i++];
            } else {
                tmp[cur++] = sortedAlphabet[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = sortedAlphabet[i++];
        }
        for(i = l; i < cur; i++){
            sortedAlphabet[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);
    }
    int minimumPushes(string word) {
        int min_cnt = 0;
        for(int i = 0 ; i < word.size(); i++){
            word_cnt[word[i] - 'a']++;
        }
        for(int i = 0 ; i < 26; i++){
            sortedAlphabet[i] = i;
        }
        merge_sort(0, 25);
        int buttonCnt = 0;
        int ans = 0;
        for(int i = 0 ; i < 26; i++){
            int c = sortedAlphabet[i];
            if (word_cnt[c] == 0) break;
            int click_cnt = buttonCnt / 8 + 1;
            ans += click_cnt*word_cnt[c];
            buttonCnt++;
        }
        return ans;
    }
};

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

Spiral Matrix III  (0) 2025.02.05
Integer to English Words  (0) 2025.02.05
Kth Distinct String in an Array  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Kth Distinct String in an Array

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

Leetcode Problem:

Summary

  • Given an array of strings and an integer k, return the kth distinct string present in the array
  • If there are fewer than k distinct strings, return an empty string.

Approach

  • The approach used is to count the frequency of each string in the array using an unordered map
  • Then, iterate through the array again to find the kth distinct string
  • If k is greater than the number of distinct strings, return an empty string.

Complexity

  • O(n + m) where n is the size of the array and m is the number of distinct strings

Explain

  • First, we create an unordered map to store the frequency of each string in the array
  • We then initialize a counter K to keep track of the number of distinct strings
  • We iterate through the array again, and for each string, we check if its frequency is 1
  • If it is, we increment the counter K
  • If K equals k, we return the current string
  • If we finish iterating through the array and K is still less than k, we return an empty string.

Solution Code:


class Solution {
public:
    string kthDistinct(vector& arr, int k) {
        unordered_map m;
        for(int i = 0 ; i < arr.size(); i++){
            m[arr[i]]++;
        }
        int K = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(m[arr[i]] == 1){
                K++;
                if(k == K) return arr[i];
            }
        }
        return "";
    }
};

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

Integer to English Words  (0) 2025.02.05
Minimum Number of Pushes to Type Word II  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Number of Senior Citizens  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Maximum Ascending Subarray Sum

알고리즘 2025. 2. 4. 23:50

Leetcode Problem:

Summary

  • Find the maximum possible sum of an ascending subarray in a given array of positive integers.

Approach

  • The approach used is to initialize variables to store the maximum sum and the current sum of the ascending subarray
  • Then, iterate over the array from the second element to the last element
  • If the current element is less than or equal to the previous element, reset the current sum to 0
  • Otherwise, add the current element to the current sum and update the maximum sum if necessary.

Complexity

  • O(n), where n is the number of elements in the array.

Explain

  • The provided solution uses Kadane's algorithm with a twist to find the maximum ascending subarray sum
  • It initializes variables `ans` and `sum` to store the maximum sum and the current sum of the ascending subarray, respectively
  • Then, it iterates over the array from the second element to the last element
  • If the current element is less than or equal to the previous element, it resets the current sum to 0
  • Otherwise, it adds the current element to the current sum and updates the maximum sum if necessary
  • The time complexity of this solution is O(n), where n is the number of elements in the array.

Solution Code:


class Solution {
public:
    vector st;
    int maxAscendingSum(vector& nums) {
        int ans = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] <= nums[i-1]){
                sum = 0;
            }
            sum += nums[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};

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

Minimum Number of Pushes to Type Word II  (0) 2025.02.05
Kth Distinct String in an Array  (0) 2025.02.05
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Number of Senior Citizens  (0) 2025.02.04
Filling Bookcase Shelves  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Range Sum of Sorted Subarray Sums

알고리즘 2025. 2. 4. 09:08

Leetcode Problem:

Summary

  • Given an array of positive integers, compute the sum of all non-empty continuous subarrays, sort them, and return the sum of a specific range in the new array.

Approach

  • The approach is to first compute the sum of all non-empty continuous subarrays, then sort them, and finally return the sum of the numbers in the specified range in the sorted array.

Complexity

  • O(n^2 log n) due to sorting, where n is the number of elements in the input array.

Explain

  • The solution code first initializes an empty array to store the subarray sums and a variable to store the sum of the current subarray
  • It then iterates over the input array, adding each number to the current sum and pushing the sum to the array
  • After each number is added, it also computes the sum of all possible subarrays starting from the current number and pushes these sums to the array
  • Finally, it sorts the array and computes the sum of the numbers in the specified range.

Solution Code:


#define MOD 1000000007
class Solution {
public:
    int rangeSum(vector& nums, int n, int left, int right) {
        vector arr;
        long long sum = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            sum %= MOD;
            arr.push_back(sum);
            long long sum2 = 0;
            for(int j = i+1 ; j < nums.size(); j++){
                sum2 += nums[j];
                sum2 %= MOD;
                arr.push_back(sum2);
            }
        }
        sort(arr.begin(), arr.end());
        long long sum3 = 0;
        for(int i = left -1; i < right; i++){
            sum3 += arr[i];
            sum3 %= MOD;
        }
        return sum3;
    }
};

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

Kth Distinct String in an Array  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
Number of Senior Citizens  (0) 2025.02.04
Filling Bookcase Shelves  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Number of Senior Citizens

알고리즘 2025. 2. 4. 09:05

Leetcode Problem:

Summary

  • The problem requires to count the number of passengers who are strictly more than 60 years old based on their details.

Approach

  • The approach used is to iterate over the details array and check the age of each passenger by comparing the 11th character (gender) and 12th character (age) with the condition
  • If the gender is 'M' or 'O' and the age is greater than 60, or if the gender is 'F' and the age is 60 or greater, then the passenger is counted as a senior.

Complexity

  • O(n) where n is the number of passengers, as we are iterating over the details array once.

Explain

  • Here's a step-by-step explanation of the solution code: 1
  • Initialize a variable `ans` to store the count of seniors. 2
  • Iterate over the `details` array using a for loop. 3
  • Inside the loop, check the age of the current passenger by comparing the 11th character (gender) and 12th character (age) with the condition. 4
  • If the gender is 'M' or 'O' and the age is greater than 60, or if the gender is 'F' and the age is 60 or greater, then increment the `ans` variable. 5
  • Return the final count of seniors after iterating over the entire array.

Solution Code:


class Solution {
public:
    int countSeniors(vector& details) {
        int ans = 0;
        for(int i = 0 ; i < details.size(); i++){
            if(details[i][11] > '6'){
                ans++;
            } else if(details[i][11] =='6' && details[i][12] > '0'){
                ans++;
            }
        }
        return ans;
    }
};

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

Maximum Ascending Subarray Sum  (0) 2025.02.04
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Filling Bookcase Shelves  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Filling Bookcase Shelves

알고리즘 2025. 2. 4. 09:02

Leetcode Problem:

Summary

  • The problem is to find the minimum possible height of a bookcase with given shelf width and a list of books, where each book has a thickness and a height.

Approach

  • Dynamic programming is used to solve this problem
  • The approach is to calculate the minimum possible height for each book and each shelf, and then choose the minimum height at each step.

Complexity

  • The time complexity of this solution is O(N^2), where N is the number of books
  • This is because there are two nested loops in the solution code.

Explain

  • The solution code uses a dynamic programming approach to solve the problem
  • It initializes an array dp of size 1001 to store the minimum possible height for each book and each shelf
  • Then, it iterates over each book and each shelf, and for each shelf, it calculates the minimum possible height by considering all possible combinations of books on the shelf
  • Finally, it returns the minimum possible height for the last book and the last shelf.

Solution Code:


class Solution {
public:
    int dp[1001];
    int minHeightShelves(vector>& books, int shelfWidth) {
        int N = books.size();
        for(int i = 1; i <= N; i++){
            int width = books[i-1][0];
            int height = books[i-1][1];
            dp[i] = dp[i-1] + height;
            for(int j = i -1; j > 0; j--){
                height = max(height, books[j-1][1]);
                width += books[j-1][0];
                if (width > shelfWidth) break;
                dp[i] = min(dp[j-1] + height, dp[i]);
            }
        }
        return dp[N];
    }
};

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

Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Number of Senior Citizens  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Minimum Deletions to Make String Balanced

알고리즘 2025. 2. 4. 08:58

Leetcode Problem:

Summary

  • Find the minimum number of deletions needed to make a string of 'a's and 'b's balanced.

Approach

  • Use a greedy approach to count the minimum number of deletions
  • Iterate through the string, incrementing the count of 'b's and decrementing the count of 'a's when a 'b' is encountered after an 'a'
  • The number of deletions is the minimum between the current count of 'b's and 0.

Complexity

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

Explain

  • The provided C++ code initializes a variable to store the minimum number of deletions and another variable to count the number of 'b's encountered so far
  • It then iterates through the string, incrementing the 'b' count when a 'b' is encountered and decrementing the 'a' count when a 'b' is encountered after an 'a'
  • The number of deletions is the minimum between the current 'b' count and 0
  • This approach ensures that the minimum number of deletions is achieved by deleting the maximum number of 'a's after a 'b' has been encountered.

Solution Code:


class Solution {
public:
    int minimumDeletions(string s) {
        int ans = 0;
        int b_cnt = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(s[i] == 'b'){
                b_cnt++;
            } else if (b_cnt > 0 && s[i] == 'a'){
                ans++;
                b_cnt--;
            }
        }
        return ans;
    }
};

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

Number of Senior Citizens  (0) 2025.02.04
Filling Bookcase Shelves  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Count Number of Teams

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

Leetcode Problem:

Summary

  • Count the number of teams that can be formed from a list of unique ratings.

Approach

  • The solution uses a two-pointer technique to count the number of teams that can be formed
  • It iterates over the list of ratings, and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating
  • The number of teams that can be formed with the current rating is then calculated by multiplying the number of ratings to its left and right that are less than and greater than the current rating, respectively
  • The total number of teams is then calculated by summing up the number of teams that can be formed for each rating.

Complexity

  • O(N^2) where N is the number of ratings.

Explain

  • The solution iterates over the list of ratings and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating
  • The number of teams that can be formed with the current rating is then calculated by multiplying the number of ratings to its left and right that are less than and greater than the current rating, respectively
  • The total number of teams is then calculated by summing up the number of teams that can be formed for each rating
  • This approach ensures that each rating is counted multiple times, but it is necessary to count the number of teams that can be formed for each rating
  • The time complexity of the solution is O(N^2) because the solution iterates over the list of ratings and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating.

Solution Code:


class Solution {
public:
    int ans = 0;
    int numTeams(vector& rating) {
        int N = rating.size();
        for(int i = 1; i < N - 1; i++){
            int leftCnt1 = 0;
            int leftCnt2 = 0;
            int idx = i - 1;
            while(idx >= 0){
                if(rating[idx] < rating[i]){
                    leftCnt1++;
                }
                if(rating[idx] > rating[i]){
                    leftCnt2++;
                }
                idx--;
            }
            int rightCnt1 = 0;
            int rightCnt2 = 0;
            idx = i + 1;
            while(idx < N){
                if(rating[i] < rating[idx]){
                    rightCnt1++;
                }
                if(rating[i] > rating[idx]){
                    rightCnt2++;
                }
                idx++;
            }
            ans += leftCnt1 * rightCnt1;
            ans += leftCnt2 * rightCnt2;
        }
        return ans;
    }
};

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

Filling Bookcase Shelves  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
Find the City With the Smallest Number of Neighbors at a Threshold Distance  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Second Minimum Time to Reach Destination

알고리즘 2025. 2. 4. 08:51

Leetcode Problem:

Summary

  • The problem is to find the second minimum time it will take to go from vertex 1 to vertex n in a bi-directional connected graph with n vertices, given the edges, time, and change.

Approach

  • The approach used is to use a priority queue to keep track of the nodes to visit, and a visited array to keep track of the nodes that have been visited
  • The time complexity is O(n log n) due to the use of the priority queue.

Complexity

  • O(n log n)

Explain

  • The solution code uses a priority queue to keep track of the nodes to visit, and a visited array to keep track of the nodes that have been visited
  • The time complexity is O(n log n) due to the use of the priority queue
  • The code first initializes the priority queue with the first node (1) and its time (0)
  • Then, it enters a loop where it pops the node with the minimum time from the priority queue, and for each of its neighbors that have not been visited before, it adds them to the priority queue with their updated time
  • The loop continues until all nodes have been visited
  • Finally, it returns the minimum time that has been visited at least twice, which is the second minimum time.

Solution Code:


struct NODE {
    int num;
    int time;

    bool operator <(NODE &b){
        return time < b.time;
    }
};

template 
struct _heap{
    int size;
    T arr[80001];
    _heap(){
        size = 1;
    }
    bool cmp(T a, T b){
        return a < b;
    }
    bool empty(){
        return size == 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx], arr[idx/2])){
            T tmp = arr[idx];
            tmp = arr[idx/2];
            arr[idx/2] = tmp;
            idx /= 2;
        }
    }
    T pop(){
        T ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size) break;
            if (j+1 < size && cmp(arr[j+1], arr[j])){
                j++;
            }
            if (cmp(arr[j], arr[i])){
                T tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    vector visited[10001];
    vector adj[10001];
    int secondMinimum(int n, vector>& edges, int time, int change) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        visited[1].push_back(0);
        for(int i = 0 ; i < adj[1].size(); i++){
            int v = adj[1][i];
            h.push({v, time});
            visited[v].push_back(time);
        }
        int minCost = 1234567890;
        int minSecondCost = 1234567890;

        while(!h.empty()){
            NODE a = h.pop();
            if (a.num == n && a.time < minCost){
                minSecondCost = minCost;
                minCost = a.time;
            }
            if (a.num == n && a.time > minCost && minSecondCost > a.time){
                minSecondCost = a.time;
            }
            for(int i = 0 ; i < adj[a.num].size(); i++){
                int next = adj[a.num][i];
                if (visited[next].size() >= 2){
                    continue;
                }
                int cost = 0;
                if ((a.time / change)%2){
                    cost = (change - (a.time%change)) + a.time + time;
                } else {
                    cost = a.time + time;
                }

                if(visited[next].size() == 0){
                    visited[next].push_back(cost);
                } else{
                    if (visited[next][0] == cost){
                        continue;
                    }
                    visited[next].push_back(cost);
                }
                h.push({next, cost});
            }
        }
        return minSecondCost;
    }
};

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

Minimum Deletions to Make String Balanced  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
Find the City With the Smallest Number of Neighbors at a Threshold Distance  (0) 2025.02.04
Sort an Array  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

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

티스토리툴바