02_array_string.c

  1/*
  2 * 배열과 문자열 (Array and String)
  3 * Two Pointer, Sliding Window, Prefix Sum
  4 *
  5 * 배열과 문자열을 효율적으로 다루는 기법들입니다.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <string.h>
 11#include <stdbool.h>
 12
 13/* =============================================================================
 14 * 1. 투 포인터 (Two Pointers)
 15 * ============================================================================= */
 16
 17/* 정렬된 배열에서 두 수의 합이 target인 쌍 찾기 */
 18bool two_sum_sorted(int arr[], int n, int target, int* i, int* j) {
 19    int left = 0, right = n - 1;
 20
 21    while (left < right) {
 22        int sum = arr[left] + arr[right];
 23        if (sum == target) {
 24            *i = left;
 25            *j = right;
 26            return true;
 27        } else if (sum < target) {
 28            left++;
 29        } else {
 30            right--;
 31        }
 32    }
 33    return false;
 34}
 35
 36/* 배열 뒤집기 */
 37void reverse_array(int arr[], int left, int right) {
 38    while (left < right) {
 39        int temp = arr[left];
 40        arr[left] = arr[right];
 41        arr[right] = temp;
 42        left++;
 43        right--;
 44    }
 45}
 46
 47/* 중복 제거 (정렬된 배열) */
 48int remove_duplicates(int arr[], int n) {
 49    if (n == 0) return 0;
 50
 51    int write = 1;
 52    for (int read = 1; read < n; read++) {
 53        if (arr[read] != arr[read - 1]) {
 54            arr[write++] = arr[read];
 55        }
 56    }
 57    return write;
 58}
 59
 60/* =============================================================================
 61 * 2. 슬라이딩 윈도우 (Sliding Window)
 62 * ============================================================================= */
 63
 64/* 고정 크기 윈도우의 최대 합 */
 65int max_sum_subarray(int arr[], int n, int k) {
 66    if (n < k) return -1;
 67
 68    int window_sum = 0;
 69    for (int i = 0; i < k; i++) {
 70        window_sum += arr[i];
 71    }
 72
 73    int max_sum = window_sum;
 74    for (int i = k; i < n; i++) {
 75        window_sum += arr[i] - arr[i - k];
 76        if (window_sum > max_sum) {
 77            max_sum = window_sum;
 78        }
 79    }
 80
 81    return max_sum;
 82}
 83
 84/* 합이 target 이상인 최소 길이 부분 배열 */
 85int min_subarray_len(int arr[], int n, int target) {
 86    int left = 0;
 87    int sum = 0;
 88    int min_len = n + 1;
 89
 90    for (int right = 0; right < n; right++) {
 91        sum += arr[right];
 92
 93        while (sum >= target) {
 94            int len = right - left + 1;
 95            if (len < min_len) min_len = len;
 96            sum -= arr[left++];
 97        }
 98    }
 99
100    return (min_len == n + 1) ? 0 : min_len;
101}
102
103/* 최대 k개 0을 1로 바꿨을 때 연속 1의 최대 길이 */
104int longest_ones(int arr[], int n, int k) {
105    int left = 0;
106    int zeros = 0;
107    int max_len = 0;
108
109    for (int right = 0; right < n; right++) {
110        if (arr[right] == 0) zeros++;
111
112        while (zeros > k) {
113            if (arr[left] == 0) zeros--;
114            left++;
115        }
116
117        int len = right - left + 1;
118        if (len > max_len) max_len = len;
119    }
120
121    return max_len;
122}
123
124/* =============================================================================
125 * 3. 프리픽스 합 (Prefix Sum)
126 * ============================================================================= */
127
128/* 프리픽스 합 배열 생성 */
129int* build_prefix_sum(int arr[], int n) {
130    int* prefix = malloc((n + 1) * sizeof(int));
131    prefix[0] = 0;
132    for (int i = 0; i < n; i++) {
133        prefix[i + 1] = prefix[i] + arr[i];
134    }
135    return prefix;
136}
137
138/* 구간 합 쿼리 [left, right] */
139int range_sum(int prefix[], int left, int right) {
140    return prefix[right + 1] - prefix[left];
141}
142
143/* 2D 프리픽스 합 */
144typedef struct {
145    int** prefix;
146    int rows;
147    int cols;
148} PrefixSum2D;
149
150PrefixSum2D* build_prefix_sum_2d(int** matrix, int rows, int cols) {
151    PrefixSum2D* ps = malloc(sizeof(PrefixSum2D));
152    ps->rows = rows;
153    ps->cols = cols;
154    ps->prefix = malloc((rows + 1) * sizeof(int*));
155
156    for (int i = 0; i <= rows; i++) {
157        ps->prefix[i] = calloc(cols + 1, sizeof(int));
158    }
159
160    for (int i = 1; i <= rows; i++) {
161        for (int j = 1; j <= cols; j++) {
162            ps->prefix[i][j] = matrix[i-1][j-1]
163                             + ps->prefix[i-1][j]
164                             + ps->prefix[i][j-1]
165                             - ps->prefix[i-1][j-1];
166        }
167    }
168
169    return ps;
170}
171
172int query_2d(PrefixSum2D* ps, int r1, int c1, int r2, int c2) {
173    return ps->prefix[r2+1][c2+1]
174         - ps->prefix[r1][c2+1]
175         - ps->prefix[r2+1][c1]
176         + ps->prefix[r1][c1];
177}
178
179void free_prefix_sum_2d(PrefixSum2D* ps) {
180    for (int i = 0; i <= ps->rows; i++) {
181        free(ps->prefix[i]);
182    }
183    free(ps->prefix);
184    free(ps);
185}
186
187/* =============================================================================
188 * 4. 문자열 처리
189 * ============================================================================= */
190
191/* 팰린드롬 검사 */
192bool is_palindrome(const char* s) {
193    int left = 0;
194    int right = strlen(s) - 1;
195
196    while (left < right) {
197        if (s[left] != s[right]) return false;
198        left++;
199        right--;
200    }
201    return true;
202}
203
204/* 애너그램 검사 */
205bool is_anagram(const char* s1, const char* s2) {
206    if (strlen(s1) != strlen(s2)) return false;
207
208    int count[26] = {0};
209
210    for (int i = 0; s1[i]; i++) {
211        count[s1[i] - 'a']++;
212        count[s2[i] - 'a']--;
213    }
214
215    for (int i = 0; i < 26; i++) {
216        if (count[i] != 0) return false;
217    }
218    return true;
219}
220
221/* 가장 긴 공통 접두사 */
222char* longest_common_prefix(char* strs[], int n) {
223    if (n == 0) return "";
224
225    char* prefix = malloc(strlen(strs[0]) + 1);
226    strcpy(prefix, strs[0]);
227
228    for (int i = 1; i < n; i++) {
229        int j = 0;
230        while (prefix[j] && strs[i][j] && prefix[j] == strs[i][j]) {
231            j++;
232        }
233        prefix[j] = '\0';
234    }
235
236    return prefix;
237}
238
239/* =============================================================================
240 * 5. Kadane 알고리즘 (최대 부분 배열 합)
241 * ============================================================================= */
242
243int max_subarray_sum(int arr[], int n) {
244    int max_ending_here = arr[0];
245    int max_so_far = arr[0];
246
247    for (int i = 1; i < n; i++) {
248        max_ending_here = (arr[i] > max_ending_here + arr[i])
249                        ? arr[i] : max_ending_here + arr[i];
250        if (max_ending_here > max_so_far) {
251            max_so_far = max_ending_here;
252        }
253    }
254
255    return max_so_far;
256}
257
258/* =============================================================================
259 * 테스트
260 * ============================================================================= */
261
262void print_array(int arr[], int n) {
263    printf("[");
264    for (int i = 0; i < n; i++) {
265        printf("%d", arr[i]);
266        if (i < n - 1) printf(", ");
267    }
268    printf("]");
269}
270
271int main(void) {
272    printf("============================================================\n");
273    printf("배열과 문자열 (Array and String) 예제\n");
274    printf("============================================================\n");
275
276    /* 1. 투 포인터 */
277    printf("\n[1] 투 포인터 - Two Sum\n");
278    int arr1[] = {2, 7, 11, 15};
279    int i, j;
280    if (two_sum_sorted(arr1, 4, 9, &i, &j)) {
281        printf("    배열: [2,7,11,15], target=9\n");
282        printf("    인덱스: (%d, %d)\n", i, j);
283    }
284
285    printf("\n[2] 중복 제거\n");
286    int arr2[] = {1, 1, 2, 2, 3, 4, 4};
287    printf("    원본: ");
288    print_array(arr2, 7);
289    int new_len = remove_duplicates(arr2, 7);
290    printf("\n    결과: ");
291    print_array(arr2, new_len);
292    printf(" (길이: %d)\n", new_len);
293
294    /* 2. 슬라이딩 윈도우 */
295    printf("\n[3] 슬라이딩 윈도우 - 최대 합\n");
296    int arr3[] = {2, 1, 5, 1, 3, 2};
297    printf("    배열: [2,1,5,1,3,2], k=3\n");
298    printf("    최대 합: %d\n", max_sum_subarray(arr3, 6, 3));
299
300    printf("\n[4] 합이 target 이상인 최소 길이\n");
301    int arr4[] = {2, 3, 1, 2, 4, 3};
302    printf("    배열: [2,3,1,2,4,3], target=7\n");
303    printf("    최소 길이: %d\n", min_subarray_len(arr4, 6, 7));
304
305    printf("\n[5] 최대 k개 0→1 변환 후 연속 1\n");
306    int arr5[] = {1, 1, 0, 0, 1, 1, 1, 0, 1};
307    printf("    배열: [1,1,0,0,1,1,1,0,1], k=2\n");
308    printf("    최대 길이: %d\n", longest_ones(arr5, 9, 2));
309
310    /* 3. 프리픽스 합 */
311    printf("\n[6] 프리픽스 합\n");
312    int arr6[] = {1, 2, 3, 4, 5};
313    int* prefix = build_prefix_sum(arr6, 5);
314    printf("    배열: [1,2,3,4,5]\n");
315    printf("    구간 합 [1,3]: %d\n", range_sum(prefix, 1, 3));
316    free(prefix);
317
318    /* 4. 문자열 */
319    printf("\n[7] 팰린드롬 검사\n");
320    printf("    'racecar': %s\n", is_palindrome("racecar") ? "true" : "false");
321    printf("    'hello': %s\n", is_palindrome("hello") ? "true" : "false");
322
323    printf("\n[8] 애너그램 검사\n");
324    printf("    'listen', 'silent': %s\n",
325           is_anagram("listen", "silent") ? "true" : "false");
326
327    /* 5. Kadane */
328    printf("\n[9] Kadane - 최대 부분 배열 합\n");
329    int arr9[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
330    printf("    배열: [-2,1,-3,4,-1,2,1,-5,4]\n");
331    printf("    최대 합: %d\n", max_subarray_sum(arr9, 9));
332
333    /* 10. 알고리즘 요약 */
334    printf("\n[10] 기법 요약\n");
335    printf("    | 기법           | 시간복잡도 | 용도                    |\n");
336    printf("    |----------------|------------|-------------------------|\n");
337    printf("    | 투 포인터      | O(n)       | 정렬 배열, 양끝 탐색    |\n");
338    printf("    | 슬라이딩 윈도우| O(n)       | 연속 부분 배열          |\n");
339    printf("    | 프리픽스 합    | O(n)/O(1)  | 구간 합 쿼리            |\n");
340    printf("    | Kadane         | O(n)       | 최대 부분 배열 합       |\n");
341
342    printf("\n============================================================\n");
343
344    return 0;
345}