문제 링크

내 코드

Prefix Sum.

0ms, 70MB

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = words.size();
        vector<int> prefixSum(n + 1, 0);
        for(int i{1};i<=n;++i) {
            prefixSum[i] = prefixSum[i-1];
            if(isVowel(words[i-1].front()) && isVowel(words[i-1].back())) {
                prefixSum[i]++;
            }
        }

        vector<int> answer;
        for(vector<int>& query : queries) {
            answer.push_back(prefixSum[query[1] + 1] - prefixSum[query[0]]);
        }
        return answer;
    }
private:
    bool isVowel(char c) {
        if(c =='a' || c== 'e' || c == 'i' || c== 'o' || c == 'u') return true;
        return false;
    }
};

Solution

Approach: Prefix Sum

• 19ms, 73.98MB
• Complexity
  • Let $M$ be the size of words and $N$ be the size of queries.
  • Time Complexity: $O(M + N)$
  • Space Complexity: $O(M)$

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words,
                             vector<vector<int>>& queries) {
        vector<int> ans(queries.size());
        unordered_set<char> vowels{'a', 'e', 'i', 'o', 'u'};
        vector<int> prefixSum(words.size());
        int sum = 0;
        for (int i = 0; i < words.size(); i++) {
            string currentWord = words[i];
            if (vowels.count(currentWord[0]) &&
                vowels.count(currentWord[currentWord.size() - 1])) {
                sum++;
            }
            prefixSum[i] = sum;
        }

        for (int i = 0; i < queries.size(); i++) {
            vector<int> currentQuery = queries[i];
            ans[i] =
                prefixSum[currentQuery[1]] -
                (currentQuery[0] == 0 ? 0 : prefixSum[currentQuery[0] - 1]);
        }

        return ans;
    }
};

GPT

이 코드는 주어진 단어 리스트에서 특정 조건을 만족하는 단어의 개수를 효율적으로 구하는 문제를 해결합니다.
핵심 개념은 누적 합(Prefix Sum)을 활용하여 빠르게 질의(queries)에 답하는 것입니다.

---

🔍 문제 이해

• words: 단어들의 리스트
• queries: [L, R] 쌍으로 주어지는 범위 질의
• 각 word가 모음(a, e, i, o, u)로 시작하고 끝나는 경우에만 카운트
• 각 [L, R]에 대해 해당 범위 내에서 조건을 만족하는 단어의 개수를 반환

---

📌 코드 분석

1️⃣ 변수 선언 및 초기화

vector<int> ans(queries.size());
unordered_set<char> vowels{'a', 'e', 'i', 'o', 'u'};
vector<int> prefixSum(words.size());
int sum = 0;

• ans: 각 쿼리의 답을 저장할 벡터 (queries.size() 크기로 초기화)
• vowels: 모음 판별을 위한 unordered_set (O(1) 탐색)
• prefixSum: 누적 합 배열
• sum: 현재까지 조건을 만족하는 단어 개수를 저장하는 변수

---

2️⃣ 누적 합(prefix sum) 계산

for (int i = 0; i < words.size(); i++) {
    string currentWord = words[i];
    if (vowels.count(currentWord[0]) &&
        vowels.count(currentWord[currentWord.size() - 1])) {
        sum++;
    }
    prefixSum[i] = sum;
}

🔥 작동 방식

• 단어의 첫 글자와 마지막 글자가 모두 모음이면 sum++
• prefixSum[i]에 현재까지의 sum 값을 저장
  → 즉, prefixSum[i]는 words[0]부터 words[i]까지 조건을 만족하는 단어 개수

✅ 누적 합을 활용하면 쿼리 처리가 O(1) 로 가능!

---

3️⃣ 쿼리 처리

for (int i = 0; i < queries.size(); i++) {
    vector<int> currentQuery = queries[i];
    ans[i] =
        prefixSum[currentQuery[1]] - 
        (currentQuery[0] == 0 ? 0 : prefixSum[currentQuery[0] - 1]);
}

🔥 작동 방식

• queries[i] = [L, R]에 대해:
  • prefixSum[R]: words[0]부터 words[R]까지 조건을 만족하는 단어 개수
  • prefixSum[L-1]: words[0]부터 words[L-1]까지 조건을 만족하는 단어 개수
  • 따라서, 범위 [L, R]의 개수는
    $\text{prefixSum}[R] - \text{prefixSum}[L-1]$
• 예외 처리: L == 0이면 prefixSum[-1]은 존재하지 않으므로 0으로 대체

✅ 각 쿼리는 O(1)로 처리 가능!

---

📌 예제 실행

vector<string> words = {"apple", "banana", "orange", "egg", "umbrella"};
vector<vector<int>> queries = { {0, 2}, {1, 3}, {2, 4} };
Solution sol;
vector<int> result = sol.vowelStrings(words, queries);

🔹 Step 1: 누적 합(prefixSum) 생성

• words = ["apple", "banana", "orange", "egg", "umbrella"]
• 모음으로 시작하고 끝나는 단어:
  • "apple" ✅
  • "banana" ❌
  • "orange" ✅
  • "egg" ✅
  • "umbrella" ✅

Index	Word	조건 만족 여부	sum	prefixSum[i]
0	"apple"	✅	1	1
1	"banana"	❌	1	1
2	"orange"	✅	2	2
3	"egg"	✅	3	3
4	"umbrella"	✅	4	4

✅ prefixSum = [1, 1, 2, 3, 4]

---

🔹 Step 2: 쿼리 처리

Query	L	R	계산	결과
{0,2}	0	2	prefixSum[2] - 0 = 2	2
{1,3}	1	3	prefixSum[3] - prefixSum[0] = 3 - 1 = 2	2
{2,4}	2	4	prefixSum[4] - prefixSum[1] = 4 - 1 = 3	3

✅ 최종 출력: [2, 2, 3]

---

⏱ 시간 복잡도 분석

연산	시간 복잡도
prefixSum 계산	$O(n)$
queries 처리	$O(q)$
전체 시간 복잡도	$O(n + q)$

✅ 효율적!

---

💡 핵심 최적화 포인트

1. 누적 합(prefix sum) 활용 → $O(n)$

   • 각 words[i]가 조건을 만족하는지 확인하고 prefixSum 업데이트
   • 한 번의 for 루프만 사용 $\rightarrow$ $O(n)$

2. 쿼리 처리 최적화 → $O(1)$

   • 누적 합을 활용해 $O(1)$ 연산으로 범위 내 개수 구하기
   • 기존 $O(nq)$보다 훨씬 빠름 (q는 쿼리 개수)

---

✅ 결론

✔ 누적 합(prefix sum) 활용한 $O(n + q)$ 풀이
✔ 빠르고 효율적인 알고리즘 🚀
✔ 범위 쿼리 문제에 자주 쓰이는 기법! 💡