[leetcode] 1456. Maximum Number of Vowels in a Substring of Given Length

안녕하세요 오늘부터 릿코드 1일 1문제(?) 를 하려고 한번 풀어봤습니다!!!

옛날 백준 풀때는 쓱쓱 잘만 했던 거 같은데....역시 안하면 까먹고 감을 잃는건 어쩔 수 없나 봅니다 ㅠㅠㅠㅠ 방법이 있나요 더 열심히 하는 방법 밖에 없죠 ㅎㅎㅎ

오늘 문제입니다.

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

문제는 간단합니다. 문자열(s) 와 수(k) 가 주어집니다.
이때, 길이가 k 인 부분문자열 중 모음(a,e,i,o,u) 의 개수가 최대인 문자열 중 모음 개수를 출력하는 것이 문제입니다.

막연하게 생각했을때는 모든 경우의 수를 전부 확인하면 되는 거 아니냐라고 생각할 수 있겠지만,,,,조건을 반드시 확인해야겠죠??

s<=1e5

입니다.

TLE 가 발생하기 딱 좋습니다 ㅎㅎ 이 문제는 그냥 전형적인 dp 문제입니다.
이전 상태값에 대한 정보를 현재 마주한 문제에 적용하여 푸는 문제죠

점화식은 이렇습니다.

dp[i] = dp[i-1] + (i 번째 문자가 Vowel letter 이면 +1) + (i-k 번째 문자가 Vowel letter -1)

class Solution {
public:
    int dp[(int)1e5+1];
    int maxVowels(string str, int k) {
        int ans=-1;

        for(int i=0;i<k;i++){
            if(i==0){
                if(checkVowel(str[i]))
                    dp[i]=1;
            }
            else{
                dp[i]=dp[i-1];
                if(checkVowel(str[i]))
                    dp[i]+=1;
            }
            ans = max(ans,dp[i]);
        }

        for(int i=k;i<str.length();i++){
            int x=0;
            if(checkVowel(str[i]))x+=1;
            if(checkVowel(str[i-k]))x-=1;

            dp[i] = dp[i-1]+x;
            ans = max(ans,dp[i]);
        }
    //    for(int i=0;i<str.length();i++)cout<<dp[i]<<" ";
        // cout<<"\n"<<ans;
        return ans;
    }
    bool checkVowel(char ch)
    {
        if(ch=='a' || ch=='e' || ch=='i'|| ch=='o'|| ch=='u')return true;
        return false;
    }
};