02_array_string.cpp

  1/*
  2 * 배열과 문자열 (Array and String)
  3 * Two Pointers, Sliding Window, Prefix Sum
  4 *
  5 * 배열과 문자열 처리의 핵심 기법들입니다.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <string>
 11#include <unordered_map>
 12#include <unordered_set>
 13#include <algorithm>
 14#include <climits>
 15
 16using namespace std;
 17
 18// =============================================================================
 19// 1. 투 포인터 (Two Pointers)
 20// =============================================================================
 21
 22// 정렬된 배열에서 두 수의 합
 23pair<int, int> twoSumSorted(const vector<int>& arr, int target) {
 24    int left = 0, right = arr.size() - 1;
 25
 26    while (left < right) {
 27        int sum = arr[left] + arr[right];
 28        if (sum == target)
 29            return {left, right};
 30        else if (sum < target)
 31            left++;
 32        else
 33            right--;
 34    }
 35
 36    return {-1, -1};
 37}
 38
 39// 물 담기 (Container With Most Water)
 40int maxArea(const vector<int>& height) {
 41    int left = 0, right = height.size() - 1;
 42    int maxWater = 0;
 43
 44    while (left < right) {
 45        int h = min(height[left], height[right]);
 46        int w = right - left;
 47        maxWater = max(maxWater, h * w);
 48
 49        if (height[left] < height[right])
 50            left++;
 51        else
 52            right--;
 53    }
 54
 55    return maxWater;
 56}
 57
 58// 세 수의 합
 59vector<vector<int>> threeSum(vector<int>& nums) {
 60    vector<vector<int>> result;
 61    sort(nums.begin(), nums.end());
 62    int n = nums.size();
 63
 64    for (int i = 0; i < n - 2; i++) {
 65        if (i > 0 && nums[i] == nums[i - 1]) continue;
 66
 67        int left = i + 1, right = n - 1;
 68        while (left < right) {
 69            int sum = nums[i] + nums[left] + nums[right];
 70            if (sum == 0) {
 71                result.push_back({nums[i], nums[left], nums[right]});
 72                while (left < right && nums[left] == nums[left + 1]) left++;
 73                while (left < right && nums[right] == nums[right - 1]) right--;
 74                left++;
 75                right--;
 76            } else if (sum < 0) {
 77                left++;
 78            } else {
 79                right--;
 80            }
 81        }
 82    }
 83
 84    return result;
 85}
 86
 87// =============================================================================
 88// 2. 슬라이딩 윈도우 (Sliding Window)
 89// =============================================================================
 90
 91// 고정 크기 윈도우 최대 합
 92int maxSumWindow(const vector<int>& arr, int k) {
 93    int n = arr.size();
 94    if (n < k) return -1;
 95
 96    int windowSum = 0;
 97    for (int i = 0; i < k; i++) {
 98        windowSum += arr[i];
 99    }
100
101    int maxSum = windowSum;
102    for (int i = k; i < n; i++) {
103        windowSum += arr[i] - arr[i - k];
104        maxSum = max(maxSum, windowSum);
105    }
106
107    return maxSum;
108}
109
110// 중복 없는 최장 부분 문자열
111int lengthOfLongestSubstring(const string& s) {
112    unordered_set<char> charSet;
113    int maxLen = 0;
114    int left = 0;
115
116    for (int right = 0; right < (int)s.length(); right++) {
117        while (charSet.count(s[right])) {
118            charSet.erase(s[left]);
119            left++;
120        }
121        charSet.insert(s[right]);
122        maxLen = max(maxLen, right - left + 1);
123    }
124
125    return maxLen;
126}
127
128// 합이 target 이상인 최소 길이 부분 배열
129int minSubArrayLen(int target, const vector<int>& nums) {
130    int n = nums.size();
131    int minLen = INT_MAX;
132    int sum = 0;
133    int left = 0;
134
135    for (int right = 0; right < n; right++) {
136        sum += nums[right];
137        while (sum >= target) {
138            minLen = min(minLen, right - left + 1);
139            sum -= nums[left];
140            left++;
141        }
142    }
143
144    return minLen == INT_MAX ? 0 : minLen;
145}
146
147// =============================================================================
148// 3. 프리픽스 합 (Prefix Sum)
149// =============================================================================
150
151class PrefixSum {
152private:
153    vector<long long> prefix;
154
155public:
156    PrefixSum(const vector<int>& arr) {
157        int n = arr.size();
158        prefix.resize(n + 1, 0);
159        for (int i = 0; i < n; i++) {
160            prefix[i + 1] = prefix[i] + arr[i];
161        }
162    }
163
164    // [left, right] 구간 합
165    long long rangeSum(int left, int right) {
166        return prefix[right + 1] - prefix[left];
167    }
168};
169
170// 합이 k인 부분 배열 개수
171int subarraySum(const vector<int>& nums, int k) {
172    unordered_map<int, int> prefixCount;
173    prefixCount[0] = 1;
174    int sum = 0;
175    int count = 0;
176
177    for (int num : nums) {
178        sum += num;
179        if (prefixCount.count(sum - k)) {
180            count += prefixCount[sum - k];
181        }
182        prefixCount[sum]++;
183    }
184
185    return count;
186}
187
188// =============================================================================
189// 4. 카데인 알고리즘 (Kadane's Algorithm)
190// =============================================================================
191
192int maxSubArray(const vector<int>& nums) {
193    int maxSum = nums[0];
194    int currentSum = nums[0];
195
196    for (size_t i = 1; i < nums.size(); i++) {
197        currentSum = max(nums[i], currentSum + nums[i]);
198        maxSum = max(maxSum, currentSum);
199    }
200
201    return maxSum;
202}
203
204// 최대 부분 배열의 인덱스도 반환
205tuple<int, int, int> maxSubArrayWithIndices(const vector<int>& nums) {
206    int maxSum = nums[0];
207    int currentSum = nums[0];
208    int start = 0, end = 0, tempStart = 0;
209
210    for (size_t i = 1; i < nums.size(); i++) {
211        if (nums[i] > currentSum + nums[i]) {
212            currentSum = nums[i];
213            tempStart = i;
214        } else {
215            currentSum += nums[i];
216        }
217
218        if (currentSum > maxSum) {
219            maxSum = currentSum;
220            start = tempStart;
221            end = i;
222        }
223    }
224
225    return {maxSum, start, end};
226}
227
228// =============================================================================
229// 5. 문자열 처리
230// =============================================================================
231
232// 팰린드롬 체크
233bool isPalindrome(const string& s) {
234    int left = 0, right = s.length() - 1;
235    while (left < right) {
236        if (s[left] != s[right]) return false;
237        left++;
238        right--;
239    }
240    return true;
241}
242
243// 애너그램 체크
244bool isAnagram(const string& s, const string& t) {
245    if (s.length() != t.length()) return false;
246
247    vector<int> count(26, 0);
248    for (size_t i = 0; i < s.length(); i++) {
249        count[s[i] - 'a']++;
250        count[t[i] - 'a']--;
251    }
252
253    for (int c : count) {
254        if (c != 0) return false;
255    }
256    return true;
257}
258
259// 문자열 압축
260string compress(const string& s) {
261    if (s.empty()) return s;
262
263    string result;
264    int count = 1;
265
266    for (size_t i = 1; i <= s.length(); i++) {
267        if (i < s.length() && s[i] == s[i - 1]) {
268            count++;
269        } else {
270            result += s[i - 1];
271            if (count > 1) {
272                result += to_string(count);
273            }
274            count = 1;
275        }
276    }
277
278    return result.length() < s.length() ? result : s;
279}
280
281// =============================================================================
282// 테스트
283// =============================================================================
284
285int main() {
286    cout << "============================================================" << endl;
287    cout << "배열과 문자열 예제" << endl;
288    cout << "============================================================" << endl;
289
290    // 1. 투 포인터
291    cout << "\n[1] 투 포인터" << endl;
292    vector<int> sorted = {1, 2, 3, 4, 6};
293    auto [idx1, idx2] = twoSumSorted(sorted, 6);
294    cout << "    배열: [1,2,3,4,6], 타겟: 6" << endl;
295    cout << "    인덱스: (" << idx1 << ", " << idx2 << ")" << endl;
296
297    vector<int> heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
298    cout << "    물 담기: " << maxArea(heights) << endl;
299
300    // 2. 슬라이딩 윈도우
301    cout << "\n[2] 슬라이딩 윈도우" << endl;
302    vector<int> arr = {1, 4, 2, 10, 23, 3, 1, 0, 20};
303    cout << "    크기 4 윈도우 최대 합: " << maxSumWindow(arr, 4) << endl;
304
305    cout << "    \"abcabcbb\" 최장 부분 문자열: " << lengthOfLongestSubstring("abcabcbb") << endl;
306
307    vector<int> nums = {2, 3, 1, 2, 4, 3};
308    cout << "    합 >= 7 최소 길이: " << minSubArrayLen(7, nums) << endl;
309
310    // 3. 프리픽스 합
311    cout << "\n[3] 프리픽스 합" << endl;
312    vector<int> prefixArr = {1, 2, 3, 4, 5};
313    PrefixSum ps(prefixArr);
314    cout << "    배열: [1,2,3,4,5]" << endl;
315    cout << "    [1,3] 구간 합: " << ps.rangeSum(1, 3) << endl;
316
317    vector<int> subarr = {1, 1, 1};
318    cout << "    합이 2인 부분 배열 개수: " << subarraySum(subarr, 2) << endl;
319
320    // 4. 카데인 알고리즘
321    cout << "\n[4] 카데인 알고리즘" << endl;
322    vector<int> kadane = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
323    cout << "    배열: [-2,1,-3,4,-1,2,1,-5,4]" << endl;
324    cout << "    최대 부분 배열 합: " << maxSubArray(kadane) << endl;
325
326    // 5. 문자열 처리
327    cout << "\n[5] 문자열 처리" << endl;
328    cout << "    \"racecar\" 팰린드롬: " << (isPalindrome("racecar") ? "예" : "아니오") << endl;
329    cout << "    \"anagram\"/\"nagaram\" 애너그램: " << (isAnagram("anagram", "nagaram") ? "예" : "아니오") << endl;
330    cout << "    \"aabcccccaaa\" 압축: " << compress("aabcccccaaa") << endl;
331
332    // 6. 복잡도 요약
333    cout << "\n[6] 복잡도 요약" << endl;
334    cout << "    | 알고리즘        | 시간복잡도 |" << endl;
335    cout << "    |-----------------|------------|" << endl;
336    cout << "    | 투 포인터       | O(n)       |" << endl;
337    cout << "    | 슬라이딩 윈도우 | O(n)       |" << endl;
338    cout << "    | 프리픽스 합     | O(1) 쿼리  |" << endl;
339    cout << "    | 카데인          | O(n)       |" << endl;
340
341    cout << "\n============================================================" << endl;
342
343    return 0;
344}