[LeetCode] Maximum Number of Vowels in a Substring of Given Length

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/?envType=study-plan-v2&envId=leetcode-75

 

Given a string s and an integer k,

return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example 1:
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:
Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.
 

Constraints:
1 <= s.length <= 105
s consists of lowercase English letters.
1 <= k <= s.length

---

문자열 s를 k만큼 잘라서 그 안에 모음이 몇 개나 들어 있는지 센다.

그리고 모음 수가 최대로 몇이 나올 수 있는지 구하는 문제.

이 문제랑 얼추 비슷한 듯 묘하게 다르다.

 

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const countVowels = (str) => {
    const vowels = ['a','e','i','o','u'];
    // 97, 101, 105, 111, 117 charCodeAt으로 비교하면 더 빠를까?
    // charCodeAt으로 변환하는 시간 때문인지 좀 더 느리다.
    let res = 0;
    for(const char of str){
        vowels.indexOf(char) > -1 && res++;
    }
    return res;
}
const maxVowels = function(s, k) {
    // string s가 주어지고 숫자 k가 주어짐. 
    // k라는 길이를 가진 s내의 문자 중 가장 많은 모음을 포함한 숫자를 리턴
    let result = 0;
    for(let i=0; i < s.length - k + 1; i++){
        const substr = s.substring(i, i+k);
        const tempResult = countVowels(substr);
        result = tempResult > result ? tempResult : result;
    }
    return result;
};

 

이것도 당연히 풀기만 하는거는 쉽다.

언제나 더 효율적으로 작동하도록 생각하는게 더 어려운 것 같다.

그래도 기존에 풀었던 문제랑 비슷해서 금방 해결할 거라고 생각했다.

 

 

아 아닌가?

그와중에 테스트케이스 중에 걸린 게 하필 tryhard라 한번 열받아주고...

 

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const vowels = ['a','e','i','o','u'];

const countVowels = (str) => {
    // 97, 101, 105, 111, 117 charCodeAt으로 비교하면 더 빠를까?
    let res = 0;
    for(const char of str){
        vowels.indexOf(char) >= 0 && res++;
    }
    return res;
}
const maxVowels = function(s, k) {
    // string s가 주어지고 숫자 k가 주어짐. 
    // k라는 길이를 가진 s내의 문자 중 가장 많은 모음을 포함한 숫자를 리턴
    let result = countVowels(s.substring(0, k)); // 초기값
    let finalResult = result;
    for(let i=k; i < s.length; i++){
        const isPrevCharVowel = vowels.indexOf(s[i-k]) > -1;
        const isNextCharVowel = vowels.indexOf(s[i]) > -1;
        result = result - isPrevCharVowel + isNextCharVowel; // boolean은 숫자랑 더하면 0, 1
        finalResult = result > finalResult ? result : finalResult;
    }
    return finalResult;
};

 

아무튼 17ms로 해결. indexOf보다는 includes가 아주 조금 더 빠르다.

이번 문제에서는 인덱스가 굳이 필요하진 않고 존재 여부만 확인하는 거니까 includes가 더 적절한 듯.

그리고, finalResult가 k와 같은 경우 더 돌지 말고 바로 리턴해버리는 것도 좋을 것 같다.

 

 

묘하게 아쉬워서 실행시간 탑을 찍은... 5ms짜리 답변을 훔왔다.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
 var checkVowel = function(e)
 {
    if(e == 'a' || e == 'e' || e == 'i' || e == 'o' || e == 'u')
    return true;

    return false;
 }
var maxVowels = function(s, k) {
    var count = 0;
    var ans = 0;
    for(var x = 0 ; x < s.length ; x++)
    {
        if(x < k)
        {
            if(checkVowel(s[x]))
            count++;
            ans = Math.max(ans,count);
        }else{
            if(checkVowel(s[x-k]))
            count--;
            if(checkVowel(s[x]))
            count++;
            ans = Math.max(ans,count);
        }
        
    }
    return ans;
};

 

for문을 그냥 문자열 길이만큼만 한 번 돌면 끝나는...

자를 문자열 길이까지는 모음이면 1을 더해주는 과정만 진행하고,

현재 인덱스가 문자열 길이를 넘어가면 이전의 잘린 문자열의 맨 앞자리(s[x-k])가 모음이면 -1,

현재 잘린 문자열의 맨 뒷자리(s[x])가 모음이면 +1 해주는 식으로...

 

원리 자체는 내가 푼 것과 동일하지만 if문을 넣어서 불필요한 계산 과정을 최소화했다.

이런 생각을 어떻게 하는 건지 정말 대단하다...