LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length

 

 

 

초기 접근 방법

❗️처음에 생각한 방향

 

for문으로 string의 길이만큼 다 돌면서 주어진 길이 k만큼씩 반복해서 일일이 찾을 생각

하지만 시간 복잡도가 O(n*n)인 것을 알기 때문에 좋지 않은 알고리즘이라고 생각함

코드 자체는 금방 짜기 때문에 일단 Brute Force로 되나 해보기나 하자라는 마음으로 

아래와 같이 구현

 

 

Brute Force

bool isVowel(char s){
    switch(s){
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':
            return true;
        default:
            return false;
    }
}

int maxVowels(char * s, int k){
    int len = strlen(s);
    int max = 0, temp = 0;

    for(int i=0; i<len; i++){
        for(int j=i; j<i+k; j++){
            if(j>len) break;
            if(isVowel(s[j])) temp++; 
        }
        if(temp > max) max = temp;
        temp = 0;
    }

    return max;
}

역시나 102 / 106 번째 Testcase에서 Time Limit Exceeded ,,

 

 

 

최종 접근

✅ 길이가 k라고 정해져 있고, 해당 길이에 대해서만 비교하면 되므로 Sliding window 알고리즘 사용

 

✅ vowel인지 계속 구분해야했기 때문에 isVowel이라는 함수를 따로 구현

 

✅ 만약 window에 새롭게 볼 배열이 vowel이라면 temp++를 하고,

window에서 배제된 [i-k]번째 배열의 원소가 vowel이라면 temp--

 

✅ 처음에 임의로 max 해둔 값과 temp값을 비교해 최종 max 값을 반환

 

 

 

구현

Runtime : 5ms

Beats 96.00% of users with C

bool isVowel(char s){
    switch(s){
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':
            return true;
        default:
            return false;
    }
}

int maxVowels(char * s, int k){
    int len = strlen(s);
    int max = 0, temp = 0;

    for(int i=0; i<k; i++){
        if(isVowel(s[i])) max++;
    }
    temp = max;

    for(int i=k; i<len; i++){
        if(isVowel(s[i])) temp++;
        if(isVowel(s[i-k])) temp--; 
        if(temp > max) max = temp;
    }

    return max;
}

 

🔽 isVowel 함수 C언어의 string 함수 중 하나인 strchr을 이용해 아래와 같이도 구현 가능

bool isVowel(char s){
	return strchr("aeiou", s) != NULL;
}

 

Take aways

✅  비교할 배열의 크기가 정해져 있다면 Sliding Window를 쓰는 것이 그냥 비교하는 것보다 좋음

이 문제에서도 k길이만큼으로 정해져 있었기 때문에 sliding window 사용

 

 

✅  반복적으로 쓰이는 함수는 코드의 간결함과 가독성을 위해 따로 구현할 것