02_array_string.py

  1"""
  2투 포인터 (Two Pointer) 기법
  3Two Pointer Technique
  4
  5두 개의 포인터를 사용하여 배열/리스트 문제를 효율적으로 해결합니다.
  6"""
  7
  8from typing import List, Tuple, Optional
  9
 10
 11# =============================================================================
 12# 1. 두 수의 합 (정렬된 배열)
 13# =============================================================================
 14def two_sum_sorted(arr: List[int], target: int) -> Optional[Tuple[int, int]]:
 15    """
 16    정렬된 배열에서 합이 target인 두 수의 인덱스 찾기
 17    시간복잡도: O(n), 공간복잡도: O(1)
 18    """
 19    left, right = 0, len(arr) - 1
 20
 21    while left < right:
 22        current_sum = arr[left] + arr[right]
 23
 24        if current_sum == target:
 25            return (left, right)
 26        elif current_sum < target:
 27            left += 1  # 합이 작으면 왼쪽 포인터를 오른쪽으로
 28        else:
 29            right -= 1  # 합이 크면 오른쪽 포인터를 왼쪽으로
 30
 31    return None
 32
 33
 34# =============================================================================
 35# 2. 세 수의 합 (3Sum)
 36# =============================================================================
 37def three_sum(arr: List[int]) -> List[List[int]]:
 38    """
 39    합이 0인 세 수의 조합 모두 찾기 (중복 제거)
 40    시간복잡도: O(n²), 공간복잡도: O(1)
 41    """
 42    arr.sort()
 43    result = []
 44    n = len(arr)
 45
 46    for i in range(n - 2):
 47        # 중복 건너뛰기
 48        if i > 0 and arr[i] == arr[i - 1]:
 49            continue
 50
 51        left, right = i + 1, n - 1
 52
 53        while left < right:
 54            total = arr[i] + arr[left] + arr[right]
 55
 56            if total == 0:
 57                result.append([arr[i], arr[left], arr[right]])
 58                # 중복 건너뛰기
 59                while left < right and arr[left] == arr[left + 1]:
 60                    left += 1
 61                while left < right and arr[right] == arr[right - 1]:
 62                    right -= 1
 63                left += 1
 64                right -= 1
 65            elif total < 0:
 66                left += 1
 67            else:
 68                right -= 1
 69
 70    return result
 71
 72
 73# =============================================================================
 74# 3. 물 담기 (Container With Most Water)
 75# =============================================================================
 76def max_water(heights: List[int]) -> int:
 77    """
 78    두 벽 사이에 담을 수 있는 최대 물의 양
 79    시간복잡도: O(n), 공간복잡도: O(1)
 80    """
 81    left, right = 0, len(heights) - 1
 82    max_area = 0
 83
 84    while left < right:
 85        # 현재 면적 계산
 86        width = right - left
 87        height = min(heights[left], heights[right])
 88        area = width * height
 89        max_area = max(max_area, area)
 90
 91        # 더 낮은 쪽의 포인터 이동
 92        if heights[left] < heights[right]:
 93            left += 1
 94        else:
 95            right -= 1
 96
 97    return max_area
 98
 99
100# =============================================================================
101# 4. 정렬된 두 배열 합병
102# =============================================================================
103def merge_sorted_arrays(arr1: List[int], arr2: List[int]) -> List[int]:
104    """
105    정렬된 두 배열을 하나의 정렬된 배열로 합병
106    시간복잡도: O(n + m), 공간복잡도: O(n + m)
107    """
108    result = []
109    i, j = 0, 0
110
111    while i < len(arr1) and j < len(arr2):
112        if arr1[i] <= arr2[j]:
113            result.append(arr1[i])
114            i += 1
115        else:
116            result.append(arr2[j])
117            j += 1
118
119    # 남은 요소 추가
120    result.extend(arr1[i:])
121    result.extend(arr2[j:])
122
123    return result
124
125
126# =============================================================================
127# 5. 중복 제거 (정렬된 배열)
128# =============================================================================
129def remove_duplicates(arr: List[int]) -> int:
130    """
131    정렬된 배열에서 중복 제거 (in-place)
132    반환값: 고유한 요소의 개수
133    시간복잡도: O(n), 공간복잡도: O(1)
134    """
135    if not arr:
136        return 0
137
138    write_idx = 1  # 다음 고유 값을 쓸 위치
139
140    for read_idx in range(1, len(arr)):
141        if arr[read_idx] != arr[write_idx - 1]:
142            arr[write_idx] = arr[read_idx]
143            write_idx += 1
144
145    return write_idx
146
147
148# =============================================================================
149# 6. 회문 검사 (Palindrome)
150# =============================================================================
151def is_palindrome(s: str) -> bool:
152    """
153    문자열이 회문인지 검사 (알파벳/숫자만 비교)
154    시간복잡도: O(n), 공간복잡도: O(1)
155    """
156    left, right = 0, len(s) - 1
157
158    while left < right:
159        # 알파벳/숫자가 아니면 건너뛰기
160        while left < right and not s[left].isalnum():
161            left += 1
162        while left < right and not s[right].isalnum():
163            right -= 1
164
165        if s[left].lower() != s[right].lower():
166            return False
167
168        left += 1
169        right -= 1
170
171    return True
172
173
174# =============================================================================
175# 7. 슬라이딩 윈도우 (최대 합)
176# =============================================================================
177def max_sum_subarray(arr: List[int], k: int) -> int:
178    """
179    크기 k인 연속 부분 배열의 최대 합
180    시간복잡도: O(n), 공간복잡도: O(1)
181    """
182    if len(arr) < k:
183        return 0
184
185    # 초기 윈도우 합
186    window_sum = sum(arr[:k])
187    max_sum = window_sum
188
189    # 윈도우 슬라이딩
190    for i in range(k, len(arr)):
191        window_sum = window_sum - arr[i - k] + arr[i]
192        max_sum = max(max_sum, window_sum)
193
194    return max_sum
195
196
197# =============================================================================
198# 테스트
199# =============================================================================
200def main():
201    print("=" * 60)
202    print("투 포인터 (Two Pointer) 기법 예제")
203    print("=" * 60)
204
205    # 1. 두 수의 합
206    print("\n[1] 두 수의 합 (정렬된 배열)")
207    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
208    target = 10
209    result = two_sum_sorted(arr, target)
210    print(f"    배열: {arr}")
211    print(f"    타겟: {target}")
212    print(f"    결과: 인덱스 {result} -> {arr[result[0]]} + {arr[result[1]]} = {target}")
213
214    # 2. 세 수의 합
215    print("\n[2] 세 수의 합 (3Sum)")
216    arr = [-1, 0, 1, 2, -1, -4]
217    result = three_sum(arr)
218    print(f"    배열: {arr}")
219    print(f"    합이 0인 조합: {result}")
220
221    # 3. 물 담기
222    print("\n[3] 물 담기 (Container With Most Water)")
223    heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
224    result = max_water(heights)
225    print(f"    높이: {heights}")
226    print(f"    최대 물의 양: {result}")
227
228    # 4. 정렬된 배열 합병
229    print("\n[4] 정렬된 두 배열 합병")
230    arr1 = [1, 3, 5, 7]
231    arr2 = [2, 4, 6, 8, 10]
232    result = merge_sorted_arrays(arr1, arr2)
233    print(f"    배열1: {arr1}")
234    print(f"    배열2: {arr2}")
235    print(f"    합병 결과: {result}")
236
237    # 5. 중복 제거
238    print("\n[5] 중복 제거 (in-place)")
239    arr = [1, 1, 2, 2, 2, 3, 4, 4, 5]
240    count = remove_duplicates(arr)
241    print(f"    원본: [1, 1, 2, 2, 2, 3, 4, 4, 5]")
242    print(f"    고유 요소 개수: {count}")
243    print(f"    결과 배열 (앞 {count}개): {arr[:count]}")
244
245    # 6. 회문 검사
246    print("\n[6] 회문 검사")
247    test_strings = ["A man, a plan, a canal: Panama", "race a car", "Was it a car or a cat I saw?"]
248    for s in test_strings:
249        result = is_palindrome(s)
250        print(f"    '{s}' -> {result}")
251
252    # 7. 슬라이딩 윈도우
253    print("\n[7] 슬라이딩 윈도우 (크기 k 최대 합)")
254    arr = [2, 1, 5, 1, 3, 2]
255    k = 3
256    result = max_sum_subarray(arr, k)
257    print(f"    배열: {arr}, k={k}")
258    print(f"    최대 합: {result}")
259
260    print("\n" + "=" * 60)
261
262
263if __name__ == "__main__":
264    main()