알고리즘 추천: 투 포인터 (Two Pointer)

✅ 개념 설명

투 포인터는 배열을 탐색할 때 두 개의 포인터를 사용해서 효율적으로 문제를 해결하는 방식입니다.
보통 정렬된 배열에서, 시간 복잡도를 줄이기 위해 사용합니다.

---

✅ 언제 쓰나?

• 정렬된 배열에서 두 수의 합
• 부분 배열 / 구간합 / 슬라이딩 윈도우
• 중복 제거 / 정렬된 리스트 병합
• 문자열 서브패턴 찾기

---

✅ 핵심 아이디어

1. 왼쪽 포인터 (L), 오른쪽 포인터 (R) 를 초기화
2. 조건에 따라 포인터를 이동시키며 배열을 탐색
3. 특정 조건(합, 길이 등)에 만족하면 정답 후보로 저장

---

📘 예제 문제: 두 수의 합 (Two Sum II - Input Array Is Sorted)

🧾 문제 설명

정렬된 배열 numbers가 주어질 때, 두 수의 합이 target이 되는 인덱스를 반환하시오.
(인덱스는 1부터 시작, 정답은 항상 존재)

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]  # 2 + 7 = 9

 

---

✅ 풀이 방식 (투 포인터)

def two_sum(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left < right:
        cur_sum = numbers[left] + numbers[right]

        if cur_sum == target:
            return [left + 1, right + 1]  # 1-based index
        elif cur_sum < target:
            left += 1
        else:
            right -= 1

---

🧪 동작 과정 설명

1. left = 0, right = 3 (2, 15 → 합 = 17)
2. 17 > 9 → right 줄임 → right = 2 (2, 11 → 13)
3. 다시 줄임 → right = 1 (2, 7 → 9 ✅) → 정답

---

🕒 시간 복잡도

• O(n) — 한 번의 while 루프로 탐색 가능
• 메모리도 O(1) — 추가 배열 사용 없음

---

✅ 코딩 테스트에서 주의할 점

• 배열이 정렬돼 있는지 확인 (아니면 정렬 후 사용)
• 포인터 이동 조건을 정확히 설계해야 함
• 슬라이딩 윈도우처럼 구간합 문제와도 유사하게 응용 가능