두시간 알고리즘 - 6일차, Sliding Window(1)

1. Grumpy BookStore Owner: 56m21s94

https://leetcode.com/problems/grumpy-bookstore-owner/

Grumpy Bookstore Owner - LeetCode

 

삽질이 심했다. 월욜아침은 이런건가. 윈도우 크기를 고정하고, 해당 범위내에서 불만족하는 고객수를 계속 체크해서, 그게 maximum인곳을 찾은뒤에, 전체 만족하는 고객수에다가 합산을 해주면된다. 

 

/**
 * @param {number[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function(customers, grumpy, minutes) {
    let left = 0; 
    let right = minutes;
    let sum = 0; // 해당 구간에 불만족한 사람, 현제는 left 부터 right앞까지
    let maxSum = 0; 
    let total = 0; // 전체 구간에서 지금 만족하는 사람, sum구간이 만약에 다 0으로 바뀌면 sum만큼 증가 가능
    
    for(let i = 0; i < customers.length; i++){   
        if(i < right && grumpy[i] === 1){
            sum += customers[i]; // 이 구간에 있는 불만족할 사람
        } 
        
        if(grumpy[i] === 0){
            total += customers[i]; // 총 만족하는 사람
        }
    }
    
    // sum을 최대화해야한다. 
    maxSum = sum;
    
    for(let i = 1; i < customers.length - (minutes - 1); i++){
        let newSum = sum;
      
        if(grumpy[left] === 1){
            newSum -= customers[left];
        }
        if(grumpy[right] === 1){
            newSum += customers[right];
        }
    
        if(maxSum < sum){
            maxSum = sum;
        }
        
        sum = newSum;
        left++;
        right++;
    }
    
    if(maxSum < sum){
        maxSum = sum;
    }
 
    return total + maxSum;
};

 

 

2. Maximum Number of Vowels in a Substring of Given Length: 12m25s94

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

Maximum Number of Vowels in a Substring of Given Length - LeetCode

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function(s, k) {
    let count = 0; 
    
    const isVowel = (l) => {
        if(['a', 'e', 'i', 'o', 'u'].includes(l)){
            return true;
        }else{
            return false;
        }
    }
    
    for(let i = 0; i < k; i++){
        if(isVowel(s[i])){
            count++;
        }
    }
    
    let maxCount = count;
    for(let i = 1; i < s.length - (k-1); i++){
        if(isVowel(s[i-1])){
            count--;
        }
        if(isVowel(s[i+k-1])){
            count++;
        }
        if(maxCount < count){
            maxCount = count;
        }
    }
    

    return maxCount;
    
};

거의 비슷한 문제

 

위의 코드가 속도가 너무 느려서 좀 개선을 해보았다. 일단 includes를 쓰는것을 그냥 논리연산으로 하도록 했고, 초반의 count계산을 위해서 for loop을 하나 돌리던것을 없앴다. 그냥 한번 쭉다읽으면서 체크하도록 했다. 

 

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function(s, k) {
   
    
    const isVowel = (ch) => {
        if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u'){
            return true;
        }else{
            return false;
        }
    }
    
 
    let count = 0; 
    let maxCount = count;
    for(let i = 0; i < s.length; i++){      
        if(i < k){
            if(isVowel(s[i])){
                count++;
            }
        }else{
            if(isVowel(s[i-k])){
                count--;
            }
            if(isVowel(s[i])){
                count++;
            }
        }
               
        if(maxCount < count){
            maxCount = count;
        }
    }


    return maxCount;
    
};

 

 

 

3. Subarrays with K Different Integers

https://leetcode.com/problems/subarrays-with-k-different-integers/

Subarrays with K Different Integers - LeetCode

시간초과가 나는 코드, 40m15s35고민하고 해설 봤당

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysWithKDistinct = function(nums, k) {
    let answer = 0; 
    
    
    for(let i = 0; i < nums.length - k + 1; i++){
        const s = new Set();
        
        for(let j = i; j < nums.length; j++){
            if(s.size <= k){
                s.add(nums[j]);
            }
            
            if(s.size === k){  
                answer++;  
            }else if(s.size > k){
                break;
            }
        }
    
    }
    
    return answer;
  
};

 

 

 

후기

3번문제는 내일 추가적으로 다시풀어보려고 한다. 오늘은 해설을 봣고