LeetCode알고리즘 Maximum Number of Vowels in a Substring of Given Length

안녕하세요. 
오늘 풀어볼 문제는 1456번 문제입니다.
중간 난이도이며 55.6%의 성공률을 보입니다.

이 문제는 슬라이딩 윈도우 섹션입니다.
그래서 출제 의도에 맞게 슬라이딩 윈도우 알고리즘을 활용해서 풀어보는 게 좋을 것 같습니다.
슬라이딩 윈도우 알고리즘은 리스트나 배열에서 범위의 값을 비교할 때 유용합니다.

문제를 살펴보겠습니다.

문자열 s와 정수 k가 주어집니다.
크기가 k인 s의 부분 문자열에서의 모음 문자의 최대 수를 반환합니다.
영어에서 모음 문자는 (a, e, i, o, u)입니다. 

주어진 예제를 살펴봅시다.

1번 예제를 살펴보면 문자열 "abciiidef"에 k는 3입니다.
k가 3이니 substring들의 길이는 모두 3이 되어야 합니다.
0부터 순서대로 가능한 substring을 표현한다면 아래와 같이 나오게 됩니다.

아래는 가능한 substring에서 vowel의 개수를 적어둔 것입니다.

iii문자열에서 모음(i)이 3개나 있네요.
그래서 정답이 3이 된다는 것!
나머지 예제도 동일하게 적용해보면 됩니다.

 

이 문제를 슬라이딩 윈도우를 사용하지 않고는 어떻게 풀까요?
저 같은 경우는 아래와 같이 큰 for를 돌면서 시작점을 두고
내부에 for를 두어 인덱스 + k 미만까지 가게 해서 거기에 포함된 모음의 개수를 구할 것 같아요.
저렇게 이중 루프를 돌게 되면 한 substring을 구할 수 있고 내부에 포함된 모음의 개수도 구할 수 있을 것 같네요. 

사실 이렇게 풀었다가 TIME LIMIT을 만났답니다.
그리고 생각난 사실 아! 이 문제 슬라이딩 윈도우 문제였잖아.

O(n^2)의 시간 복잡도로 밀어 붙힌 결과는 처참.
응 다시 해.

아래는 슬라이딩 윈도우로 푼 코드입니다.

func maxVowels(_ s: String, _ k: Int) -> Int {
    let vowels: Set<Character> = ["a", "o", "e", "i", "u"]
    let array: Array<Character> = Array(s)
    var answer: Int = 0
    var temp: Int = 0

    for index in 0..<array.count {
        let character = array[index]
        if vowels.contains(character) {
            temp = temp + 1
        }
        if index >= k {
            let remove = array[index-k]
            if vowels.contains(remove) {
                temp = temp - 1
            }
        }
        answer = max(temp, answer)
    }
    return answer
}

vowels을 집합에 넣은 이유는 set에 contains를 사용하려고 사용했어요.
해당 메소드는 O(1)의 시간 복잡도를 가집니다. 
array는 문자열을 문자 배열로 만들어놓은 것입니다. 

여기까지 사전 세팅.
for 루프를 돌면서 진행되는 과정은 아래와 같습니다.

너무  길어서 5번째 루프까지만...
여기서 핵심은 4번째 루프부터 나타나네요.
슬라이딩 윈도우 알고리즘에 맞게 범위를 정해서 값을 비교하는데 이전에 포함되었던 것은 지우는 작업도 필요합니다.
(4번 루프에서는 temp에 1 빼 주는 작업)

 

제출해보니 아래처럼 결과가 뜨네요!
(이건 언어별로 달라서 같은 언어에서만 참고해주세요)

LeetCode는 런타임, 메모리 사용량이 나와서 좋은 것 같아요.
코드 좀 바꿔보고 실행시켜보고 런타임, 메모리 사용량 비교해보고 그렇게 개선해나가는 과정이 눈에 보여서 신기하네요.

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